f# - 如何计算F#中二叉树中非空节点的数量

Question

考虑二叉树代数数据类型

type btree = Empty | Node of btree * int * btree

和一个新的数据类型定义如下:

 type finding = NotFound | Found of int

到目前为止，这是我的代码:

let s = Node (Node(Empty, 5, Node(Empty, 2, Empty)), 3, Node (Empty, 6, Empty))
(*
     (3)
    /    \
   (5)   (6)
   / \   |  \
  () (2) () ()
 / \
() ()
*)

(* size: btree -> int *)
let rec size t =
    match t with
    Empty -> false
  | Node (t1, m, t2) -> if (m != Empty) then sum+1 || (size t1) || (size t2)

let num = occurs s
printfn "There are %i nodes in the tree" num

这可能不是很接近，我采用了一个函数来查找树中是否存在整数，并尝试更改我正在尝试执行的操作的代码。

我刚开始使用 F#，非常感谢任何帮助。我正在尝试计算树中的所有非空节点。例如，我正在使用的树应该打印值 4。

Answer 1

我没有在您的代码上运行编译器，但我相信这甚至可以编译。但是，您在递归函数中使用模式匹配的想法很好。正如 rmunn 评论的那样，您想确定每种情况下的节点数:空树没有节点，因此结果为零。一棵非空树，至少有根节点加上它的左右子树的数量。

所以按照下面的思路应该可以工作

let rec size t =
    match t with
    | Empty -> 0
    | Node (t1, _, t2) -> 1 + (size t1) + (size t2)

这里最重要的细节是，您不需要全局变量 sum 来存储任何中间值。递归函数的整体思想是那些中间值是递归调用的结果。

作为评论，我相信你在评论中的树应该是这样的。

(*
     (3)
    /    \
   (5)   (6)
   / \   |  \
  () (2) () ()
     / \
    () ()
*)

编辑:我将未对齐的 () 误读为空树的叶子，而实际上它们是子树 (2) 的叶子。所以这只是一个 ASCII 艺术问题 :-)