Haskell满二叉树判断函数fullA测试结果异常问题求助
满二叉树判断函数的异常成因
核心问题定位
你当前实现对单分支节点One的判断逻辑存在本质偏差,这也是测试用例输出异常的根本原因。
首先对齐满二叉树的判定标准:所有非叶子节点必须恰好拥有两个子节点,整棵树中不存在任何单分支结构的节点。
错误执行流复现
针对测试用例fullA (One 0 (One 1 (Leaf 2))),按照你编写的函数逻辑逐层递归计算的过程如下:
- 最内层
Leaf 2匹配叶子分支规则,返回True - 中间层
One 1 (Leaf 2)匹配单分支规则,执行not (fullA (Leaf 2)),得到结果False - 最外层
One 0 (One 1 (Leaf 2))再次匹配单分支规则,执行not (fullA (One 1 (Leaf 2)))——也就是对中间层的结果再做一次取反,最终得到not False = True
两次连续的单分支判断形成了“负负得正”的取反抵消效果,直接输出了不符合预期的True结果。
逻辑偏差根源
原函数对One单分支节点的判断写为not (fullA b),本质是把“单分支节点是否合规”和“子树是否合规”做了反向绑定:只要子树不是满二叉树,当前单分支节点就算合规。这套逻辑完全不匹配满二叉树的判定规则——实际上只要当前节点是单分支结构,无论子树是什么形态,整棵树都不可能是满二叉树,根本不需要递归判断子树的状态。
修正方案
仅需调整单分支节点的判断规则,去掉不必要的取反递归即可:
fullA :: AltTree a -> Bool -- 叶子节点天然满足满二叉树要求 fullA (Leaf a) = True -- 单分支节点直接判定为不符合,无需递归子树 fullA (One a b) = False -- 双分支节点需两个子树同时满足满二叉树要求 fullA (Two a b c) = fullA b && fullA c
调整后再运行原测试用例,最外层匹配One构造子会直接返回False,和预期结果完全一致。
内容的提问来源于stack exchange,提问作者Jackson Zhu
相关产品推荐
相关产品推荐

