Haskell整数二叉树最大值函数实现咨询

嘿，作为Haskell新手，能从递归数据类型入手真的很棒！你的Tree定义完全没问题，而maxInt函数正好能帮你理解递归模式匹配——这是Haskell处理树形结构的核心技巧之一，咱们一步步来实现它。

首先，先明确你的树结构定义：

data Tree = Node Int Tree Tree | Leaf Int deriving (Eq,Show)

这个类型有两种构造器：

• Leaf Int：没有子节点的叶子节点，只存一个整数
• Node Int Tree Tree：带有一个整数值、左右两棵子树的内部节点

要找整棵树的最大值，我们可以针对这两种构造器分别处理：

1. 处理叶子节点（递归终止条件） #

对于Leaf x来说，树里只有这一个整数，所以最大值就是它本身：

maxInt (Leaf x) = x

2. 处理内部节点（递归逻辑） #

对于Node x left right，最大值需要从三个地方里找：

• 当前节点的数值x
• 左子树left的最大值（递归调用maxInt left）
• 右子树right的最大值（递归调用maxInt right）

Haskell的maximum函数可以直接取列表中的最大值，所以我们可以把这三个值放进列表里，一次性拿到最大值：

maxInt (Node x left right) = maximum [x, maxInt left, maxInt right]

如果你不想用maximum，也可以用max函数两两比较（因为max只能接受两个参数）：

maxInt (Node x left right) = x `max` (maxInt left `max` maxInt right)

测试你的例子 #

现在试试你给出的测试用例：

maxInt (Node 5 (Leaf 7) (Leaf 2))

计算过程是：

• 左子树Leaf 7的最大值是7
• 右子树Leaf 2的最大值是2
• 当前节点值是5
• 三个数的最大值是7，完全符合预期！

你还可以试试更复杂的树，比如：

maxInt (Node 3 (Node 9 (Leaf 1) (Leaf 4)) (Leaf 6)) -- 应该返回9

递归的核心就是把大问题拆成更小的同类型问题，直到遇到最简单的情况（这里就是Leaf），再把结果逐层合并回来。多写几次这种递归函数，你很快就能掌握Haskell的精髓啦！

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