使用foldTree实现Tree的height函数：求解height_c与height_b定义

首先明确foldTree的工作逻辑：
这是针对二叉树的折叠函数，遍历树的每个节点时：

• 遇到Tip（空节点），直接返回传入的基准值b；
• 遇到Bin x l r（非空节点），先递归计算左子树l和右子树r的折叠结果，再用组合函数c把当前节点的值x、左子树结果、右子树结果合并，得到当前节点的最终结果。

基准情况height_b的确认 #

你的判断是对的：height_b对应空树Tip的高度，定义为0是合理的（如果把空节点视为高度为0的话；另一种常见定义是-1，但这里按你的设定来）。

组合函数height_c的实现 #

树的高度定义为：非空节点的高度 = 左右子树高度的最大值 + 1（当前节点自身占一层）。
height_c的参数分别是当前节点的值、左子树高度、右子树高度，我们只需要基于后两个值计算当前节点的高度即可，当前节点的值不影响高度，所以可以忽略第一个参数：

height_c :: a -> Int -> Int -> Int
height_c _ left right = 1 + max left right

完整实现 #

把这些代入框架后，完整代码如下：

data Tree a
= Tip
| Bin a (Tree a) (Tree a) 
deriving (Show)

foldTree
:: (a -> b -> b -> b)   -- combining function
-> b                    -- base case
-> Tree a               -- input tree
-> b                    -- answer
foldTree c b (Bin x l r) = c x (foldTree c b l) (foldTree c b r)
foldTree c b Tip         = b

height :: Tree a -> Int
height = foldTree height_c height_b

height_c :: a -> Int -> Int -> Int
height_c _ left right = 1 + max left right

height_b :: Int
height_b = 0

验证示例 #

• 空树：height Tip → 返回0，符合预期；
• 单个节点：height (Bin 5 Tip Tip) → 调用height_c 5 0 0，返回1 + max 0 0 = 1，正确；
• 两层树：height (Bin 3 (Bin 1 Tip Tip) Tip) → 左子树高度为1，右子树为0，返回1 + max 1 0 = 2，正确。

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