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]
by tnomura9
| 2009-08-14 08:21
| Haskell
|
Comments(0)
|
カテゴリ
新型コロナウイルス 主インデックス Haskell 記事リスト 圏論記事リスト 考えるということのリスト 考えるということ ラッセルのパラドックス Haskell Prelude Ocaml ボーカロイド 圏論 jQuery デモ HTML Python ツールボックス XAMPP Ruby ubuntu WordPress 脳の話 話のネタ リンク 幸福論 キリスト教 心の話 メモ 電子カルテ Dojo JavaScript C# NetWalker ed と sed HTML Raspberry Pi C 言語 命題論理 以前の記事
最新のトラックバック
最新のコメント
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||