检查一棵树是否是一棵完美的树

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。这实际上更容易实现，因为您实际上已经从递归调用中获得了高度，因此您可以比较它们。 （提示：使用符号）

perfectTree然后就是这个函数的简单包装。

import Data.Maybe (isJust) 

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

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

Answer 2

您是否试图对此进行递归思考？

---

解决方案：树的子树必须所有是完美的树木。而且，这些子树的深度应该是相等的。 结束。

我希望这个高层次的解决方案/想法有所帮助。我避免给出perfectTree的实际定义，因为我缺少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) = ??? 

工业第二种情况（ ???），我们想要在子树的高度上加一个，但只有当它们是完美的，并且只有它们具有相同的高度时。让我们定义一个帮助函数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