检查树是否是完美树

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 = ...