tree - SML二叉树归约函数

Question

所以我有一个 SML 的任务，我需要一些帮助才能开始。

问题是这样的

编写一个类型为 'a btree -> int 的函数 btree_size，它返回二叉树的大小。（二叉树的大小是二叉树中元素的数量）。例如，btree_size (Node (Leaf, 1, Node (Leaf, 2, Leaf))) 应返回 2。您的函数必须使用提供的 btree_reduce 函数，并且最多应为 3 行。

btree_reduce 函数是这样的

(* A reduction function. *)
     (* btree_reduce : ('b * 'a * 'b -> 'b) -> 'b -> 'a tree -> 'b) *)
    fun btree_reduce f b bt =
      case bt of
      Leaf => b
      | Node (l, x, r) => f (btree_reduce f b l, x, btree_reduce f b r)

我到底如何制作一个 btree_size 函数，它接受一个 btree 并使用 reduce 函数来给我树的大小？

Answer 1

由于这是作业，我将避免直接回答。:)

我将按以下方式进行：

• 熟悉计算树的大小（通过编写符合您的规范的递归函数）
• 查看您编写的函数和 btree_reduce 之间的共同点（或者，可以从您编写的函数中抽象出什么）

当然，这是众多方法之一。