haskell - 如何检查树是否是满二叉树

Question

这样fullA atr就可以判断fullA atr是否是满二叉树。

fullA :: AltTree a -> Bool
fullA (Leaf a) = True
fullA (One a b) = not (fullA b)
fullA (Two a b c) = fullA b && fullA c

它适用于大多数示例，但是当我使用示例时: fullA(One 0(One 1(Leaf 2))) 它返回 True，但应该返回 False。 有人可以给我解释一下吗？

Answer 1

带有(One a b)的行没有多大意义，因为 full tree is defined as [wiki] :

A full binary tree (sometimes referred to as a proper or plane binary tree) is a tree in which every node has either 0 or 2 children.

这意味着，如果您的 AltTree 包含 One 节点，那么它不是完整的二叉树。因此，我们可以将其实现为:

fullA :: AltTree a -> Bool
fullA (Leaf _) = True
fullA (One _ _) = <b>False</b>  -- we found a node with one one child
fullA (Two _ b c) = fullA b && fullA c

---

Note: In Haskell, it is common to use an underscore (_) for variables we do not care about. If we turn on the -Wunused-matches compiler flag, it will warn about patterns where the variables are not used at the right side of the equation.