如何在Haskell中判断二叉树是否为符合指定定义的完全二叉树

原有代码的核心问题 #

现有代码存在三个基础错误，导致无法实现目标功能：

• 数据结构定义不符合二叉树要求：你写的Node a [Tree a]是多叉树的定义，二叉树的内部节点应该固定包含左右两个子树
• 函数签名错误：判断单棵树是否符合规则，仅需传入1个树参数，不需要2个入参
• 匹配逻辑完全不成立：Leaf和Node是完全不同的代数数据类型构造子，二者的恒等判断永远返回False，没有实际逻辑意义

实现思路 #

按照题目给出的规则（每个节点的两个子树大小均相等），我们可以分两步实现：

1. 先写一个辅助函数计算任意一棵树的节点总数量
2. 递归判断规则：
   • 叶子节点没有子树，天然符合要求，直接返回True
   • 内部节点需要同时满足三个条件：
     • 左右子树的节点总数相等
     • 左子树本身符合完全二叉树要求
     • 右子树本身符合完全二叉树要求

标准二叉树结构实现代码 #

-- 修正二叉树定义：Leaf为叶子节点，Node存储节点值、左子树、右子树
data Tree a = Leaf a | Node a (Tree a) (Tree a) deriving (Eq, Show)

-- 辅助函数：计算树的节点总数
treeSize :: Tree a -> Int
treeSize (Leaf _) = 1
treeSize (Node _ left right) = 1 + treeSize left + treeSize right

-- 符合题目要求的判断函数
judcomplete :: Tree a -> Bool
judcomplete (Leaf _) = True
judcomplete (Node _ left right) = 
  treeSize left == treeSize right && judcomplete left && judcomplete right

适配原有多叉树结构的实现 #

如果你需要保留原来的Node用列表存储子树的定义，可以使用下面的兼容版本，额外增加了子树数量必须为2的校验：

data Tree a = Leaf a | Node a [Tree a] deriving (Eq, Show)

treeSize :: Tree a -> Int
treeSize (Leaf _) = 1
treeSize (Node _ children) = 1 + sum (map treeSize children)

judcomplete :: Tree a -> Bool
judcomplete (Leaf _) = True
judcomplete (Node _ children) =
  length children == 2 && 
  treeSize (children !! 0) == treeSize (children !! 1) &&
  all judcomplete children

内容的提问来源于stack exchange，提问作者Richard Hu