Haskell 99問 (54A-60)

Haskell 99問 (54A-60) 二分木(リンクのみ)

http://www.haskell.org/haskellwiki/99_questions/54A_to_60

問題54A 二分木のデータ型を定義せよ。

解答
data Tree a = Empty | Branch a (Tree a) (Tree a)
        deriving (Show, Eq)

2分木の例
tree1 = Branch 'a' (Branch 'b' (Branch 'd' Empty Empty)
                              (Branch 'e' Empty Empty))
                  (Branch 'c' Empty
                              (Branch 'f' (Branch 'g' Empty Empty)
                                          Empty)))

問題55 完全平衡木をつくる関数を作れ。完全平衡木とはその木構造のどのノードについても、右につながる枝のノード数と、左につながる枝のノード数の差が1以下になるものである。

完全平衡木の例
*Main> cbalTree 4
[
-- permutation 1
--     x
--    / \
--   x   x
--        \
--         x
Branch 'x' (Branch 'x' Empty Empty)
           (Branch 'x' Empty
                       (Branch 'x' Empty Empty)),

-- permutation 2
--     x
--    / \
--   x   x
--      /
--     x
Branch 'x' (Branch 'x' Empty Empty)
           (Branch 'x' (Branch 'x' Empty Empty)
                       Empty),

-- permutation 3
--     x
--    / \
--   x   x
--    \
--     x
Branch 'x' (Branch 'x' Empty
                       (Branch 'x' Empty Empty))
           (Branch 'x' Empty Empty),

-- permutation 4
--     x
--    / \
--   x   x
--  /
-- x
Branch 'x' (Branch 'x' (Branch 'x' Empty Empty)
                       Empty)
           (Branch 'x' Empty Empty)
]

解答
data Tree a = Empty | Branch a (Tree a) (Tree a)
        deriving (Show, Eq)

cbalTree 0 = [Empty]
cbalTree n = [Branch 'x' l r | i <- [q .. q + r], l <- cbalTree i, r <- cbalTree (n - i - 1)]
  where (q, r) = quotRem (n-1) 2

問題56 二分木が対称木であるかどうかを判別せよ。

用例:
Main> symmetric (Branch 'x' (Branch 'x' Empty Empty) Empty)
False
Main> symmetric (Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty))
True

解答:
data Tree a = Empty | Branch a (Tree a) (Tree a)
        deriving (Show, Eq)

mirror Empty Empty = True
mirror (Branch _ a b) (Branch _ x y) = mirror a y && mirror b x
mirror _ _ = False

symmetric Empty = True
symmetric (Branch _ l r) = mirror l r

問題57 整数値のリストから二分探索木を作る関数を作れ。

動作例:
Main> construct [3,2,5,7,1]
Branch 3 (Branch 2 (Branch 1 Empty Empty) Empty) (Branch 5 Empty (Branch 7 Empty Empty))

解答:
data Tree a = Empty | Branch a (Tree a) (Tree a)
        deriving (Show, Eq)

add :: Ord a => a -> Tree a -> Tree a
add x Empty            = Branch x Empty Empty
add x t@(Branch y l r) = case compare x y of
                            LT -> Branch y (add x l) r
                            GT -> Branch y l (add x r)
                            EQ -> t

construct xs = foldl (flip add) Empty xs

問題58 n 個のノードを持つ平衡木を作り、そのうちから対称木になっているものを選び出せ。

用例:
Main> symCbalTrees 5
[Branch 'x' (Branch 'x' Empty (Branch 'x' Empty Empty)) (Branch 'x' (Branch 'x' Empty Empty) Empty),Branch 'x' (Branch 'x' (Branch 'x' Empty Empty) Empty) (Branch 'x' Empty (Branch 'x' Empty Empty))]

解答:
data Tree a = Empty | Branch a (Tree a) (Tree a)
deriving (Show, Eq)

symCbalTrees = filter symmetric . cbalTree

cbalTree 0 = [Empty]
cbalTree n = [Branch 'x' l r | i <- [q .. q + r], l <- cbalTree i, r <- cbalTree (n - i - 1)]
where (q, r) = quotRem (n-1) 2

mirror Empty Empty = True
mirror (Branch _ a b) (Branch _ x y) = mirror a y && mirror b x
mirror _ _ = False

symmetric Empty = True
symmetric (Branch _ l r) = mirror l r

問題59 高さ平衡木(各ノードの左右の部分木の高さの差が1以下の2分木)を作れ。

用例:
Main> take 4 $ hbalTree 'x' 3
[Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty (Branch 'x' Empty Empty)),
Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' (Branch 'x' Empty Empty) Empty),
Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty)),
Branch 'x' (Branch 'x' Empty (Branch 'x' Empty Empty)) (Branch 'x' Empty Empty)]

解答:
data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)

hbalTree x = map fst . hbalTree'
    where hbalTree' 0 = [(Empty, 0)]
          hbalTree' 1 = [(Branch x Empty Empty, 1)]
          hbalTree' n =
                let t = hbalTree' (n-2) ++ hbalTree' (n-1)
                in  [(Branch x lb rb, h) | (lb,lh) <- t, (rb,rh) <- t
                                         , let h = 1 + max lh rh, h == n]
[PR]
by tnomura9 | 2009-08-14 08:21 | Haskell | Comments(0)
<< Haskell 99問 (61... Haskell 99問 (46... >>