Haskell递归遍历二叉树返回树结构（剔除零节点）的实现疑问

问题根源 #

你现有代码的核心错误是：当遇到值为0的节点时，仅递归处理左子树并直接返回，完全丢弃了右子树的处理逻辑，也没有对左右子树的处理结果做合并判断，因此只会保留左子树的遍历结果。

修正思路 #

遇到值为0的节点时，遵循以下逻辑处理：

1. 先递归处理当前节点的左、右子树，得到处理后的左右子树l'和r'
2. 若处理后的左子树l'非空，用l'替代当前被删除的0值节点
3. 若处理后的左子树为空，用r'替代当前被删除的0值节点

实现代码 #

首先约定你的二叉树结构定义如下（和你代码中用到的构造子对齐）：

data Tree = Void | Node Tree Int Tree deriving (Show)

修正后的modTree函数：

modTree :: Tree -> Tree
modTree Void = Void
modTree (Node l x r)
    | x == 0 = 
        let l' = modTree l
            r' = modTree r
        in if l' /= Void then l' else r'
    | otherwise = Node (modTree l) x (modTree r)

效果验证 #

你给出的测试用例原树结构对应代码定义为：

originTree :: Tree
originTree = Node 
    (Node 
        (Node Void 0 Void) 
        0 
        (Node Void 1 Void)
    ) 
    5 
    (Node Void 2 Void)

执行modTree originTree得到的结果为：

Node (Node Void 1 Void) 5 (Node Void 2 Void)

完全符合你给出的预期输出结构。

扩展说明 #

如果你的业务中删除节点的合并规则不同（例如需要把右子树挂载到左子树的最右叶子节点后），只需要调整x==0分支中的合并逻辑即可，不需要修改整体递归框架。

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