2

木が完全な木かどうかをチェックする Haskell 関数を書きたいと思います。木のすべての葉が同じ深さにあれば、その木は完璧であることを私は知っています。

私はこのように始めることを知っています

perfectTree :: Tree a -> Bool

しかし、実際の定義に対する私の理解はそれほど強くないので、完全なツリーとは何か、Haskell でツリーが完全であることを確認する方法を実際に説明できる人はいますか?

次のようにデータ型を定義したことを含める必要がありました。

data Tree a = Leaf | Node a (Tree a) (Tree a)
4

3 に答える 3

7

1つの方法は、ツリーが完全である場合、またはそれ以外の場合にツリーの高さperfectTreeHeight :: Tree a -> Maybe Intを返すヘルパー関数を定義することです。再帰呼び出しから実際に高さを取得して比較できるため、これは実装がはるかに簡単です。（ヒント：do-notationを使用してください）JustNothing

perfectTreeこの場合、はこの関数の簡単なラッパーです。

import Data.Maybe (isJust)

perfectTree :: Tree a -> Bool
perfectTree = isJust . perfectTreeHeight

perfectTreeHeight :: Tree a -> Maybe Int
perfectTreeHeight = ...
于 2012-10-18T05:12:55.507 に答える
4

これについて再帰的に考えようとしましたか？

解決策：ツリーのサブツリーはすべて完全なツリーである必要があります。また、これらのサブツリーの深さは等しくなければなりません。終わり。

この高レベルのソリューション/アイデアがお役に立てば幸いです。perfectTreeの実際の定義がないため、実際の定義を与えることは避けましたTree。

于 2012-10-18T05:13:26.550 に答える
1

あなたの木はこのように見えると思います...

data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving Show

heightここで、次の行に沿って再帰関数を定義できます。

height :: Tree a -> Maybe Int
height (Leaf _) = Just 1
height (Branch a b) = ???

2 番目のケース (???) では、サブツリーの高さに 1 を追加しますが、それらが完全であり、同じ高さである場合に限ります。sameサブツリーの高さを取り、サブツリーの高さを含む Maybe Int を返すヘルパー関数 を定義しましょう。

same :: Eq a => Maybe a -> Maybe a -> Maybe a
same (Just a) (Just b) = if a == b then Just a else Nothing
same _ _ = Nothing

これで機能を終了できheightます。サブツリーの高さに 1 を追加するだけです。

height :: Tree a -> Maybe Int
height (Leaf _) = Just 1
height (Branch a b) = maybe Nothing (Just . (1+)) subTreeHeight
  where subTreeHeight = same (height a) (height b)

で、使い方はこちら。

main :: IO ()
main = do
  let aTree = (Leaf 'a')
  print aTree
  print $ height aTree

  let bTree = Branch (Leaf 'a') (Leaf 'b')
  print bTree
  print $ height bTree

  let cTree = Branch (Leaf 'a') (Branch (Leaf 'b') (Leaf 'c'))
  print cTree
  print $ height cTree

  let dTree = Branch (Branch (Leaf 'a') (Leaf 'b')) (Branch (Leaf 'c') (Leaf 'd'))
  print dTree
  print $ height dTree

これを実行すると、次のようになります。

Leaf 'a'
Just 1
Branch (Leaf 'a') (Leaf 'b')
Just 2
Branch (Leaf 'a') (Branch (Leaf 'b') (Leaf 'c'))
Nothing
Branch (Branch (Leaf 'a') (Leaf 'b')) (Branch (Leaf 'c') (Leaf 'd'))
Just 3
于 2012-10-18T15:39:37.423 に答える