OCaml N叉树递归函数leaf_cost的递归执行步骤分析疑问

类型定义 #

type 'a ntree = Ntree of 'a * 'a ntree list 

该类型为多态N叉树：每个节点由Ntree构造器生成，第一个参数为当前节点存储的值，第二个参数为子树构成的列表，子树列表为空时代表当前节点是叶子节点。

辅助函数maxpair解析 #

let rec maxpair = function
  | [] -> failwith "empty list"
  | [(x, y)] -> (x, y)
  | (x, y) :: (a, b) :: rest -> 
      if y > b then maxpair ((x, y) :: rest) 
      else maxpair ((a, b) :: rest)

功能：输入元素为(值, 代价值)的二元组列表，返回列表中代价值最大的二元组。
执行逻辑：

• 输入空列表直接抛出异常
• 列表仅有一个二元组时直接返回该元组
• 列表长度≥2时，比较前两个二元组的代价值，丢弃代价值更小的元组后递归处理剩余列表，最终得到全局代价值最大的二元组

主函数leaf_cost解析 #

let rec leaf_cost = function
  | Ntree (x, []) -> (x, x)
  | Ntree (x, tlist) -> 
      let (y, c) = maxpair (List.map leaf_cost tlist)
      in 
      (y, c + x)

功能：输入存储整数的N叉树，返回二元组(代价最高的叶子节点的值, 根到该叶子的路径总代价)。

基础分支（叶子节点处理） #

当匹配到Ntree(x, [])时，当前节点本身就是叶子，根到该叶子的路径仅包含自身，因此直接返回(x, x)：第一个值为叶子节点本身的存储值，第二个值为路径总代价。

递归分支（非叶子节点处理） #

你困惑的let (y, c) ... in (y, c + x)逻辑按顺序拆解如下：

1. 先对当前节点的所有子树分别调用leaf_cost：List.map leaf_cost tlist会生成一个二元组列表，每个元素对应一棵子树中「代价最高的叶子值 + 该叶子到当前子树根节点的路径总代价」
2. 调用maxpair从上述列表中选出代价值最大的二元组，解构赋值给(y, c)：此时y是所有子树中代价最高的叶子的存储值，c是该叶子到当前节点的子节点的路径总代价
3. 最终返回(y, c + x)：代价最高的叶子还是y，路径总代价需要加上当前节点的存储值x，才是该叶子到当前节点的总路径代价

执行示例 #

以简单N叉树Ntree(2, [Ntree(3, []); Ntree(5, [])])为例：

• 对两个叶子子树调用leaf_cost得到列表[(3, 3), (5, 5)]
• maxpair筛选出代价值最大的元组(5, 5)，赋值y=5、c=5
• 加上当前节点值2，最终返回(5, 7)，即最高代价叶子为5，根到该叶子的路径和为2+5=7，符合预期

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