haskell - 检查一棵树是否是完美树

Question

我想编写一个 Haskell 函数来检查一棵树是否是一棵完美的树。我知道如果树的所有叶子都在相同的深度，那么一棵树就是完美的。

我知道我会这样开始

perfectTree :: Tree a -> Bool

但是看到我对实际定义的掌握不是太强，任何人都可以真正解释什么是完美的树，以及如何在 Haskell 中检查一棵树是否完美

我应该包括我定义的数据类型如下：

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

Answer 1

一种方法是定义一个辅助函数perfectTreeHeight :: Tree a -> Maybe Int，如果它是完美的，则返回Just树的高度，Nothing否则。这更容易实现，因为您实际上从递归调用中获得了高度，因此您可以比较它们。（提示：使用do-notation）

perfectTree那么只是这个函数的一个简单的包装器。

import Data.Maybe (isJust)

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

perfectTreeHeight :: Tree a -> Maybe Int
perfectTreeHeight = ...

Answer 2

您是否尝试过递归地思考这个问题？

---

解：树的子树必须都是完美树。此外，这些子树的深度应该相等。结尾。

我希望这个高级解决方案/想法有所帮助。我避免给出实际定义，perfectTree因为我缺乏 a 的实际定义Tree。

Answer 3

我假设你的树看起来像这样......

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) = ???

Ind the second case (???), we want to add one to the height of the subtrees, but only if they are perfect, and only if they have the same height. Let's define a helper function, same, which takes the heights of the subtrees, and returns a Maybe Int containing their height, but only if they are both perfect and have the same height.

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

Now we can finish the height function. All it needs to do is add 1 to the height of the subtrees.

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)

And here's how to use it.

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

When I run this, I get:

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