algorithm - 层次二叉树遍历的魔法代码——发生了什么？

Question

我们有一个二叉树的定义:

type 'a tree =
  | Node of 'a tree * 'a * 'a tree
  | Null;;

还有一个很有用的遍历树的函数"

let rec fold_tree f a t =
  match t with
  | Null -> a
  | Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);;

这是一个“魔法”函数，当给定一棵二叉树时，它返回一个列表，其中我们有特定级别的元素列表，例如，当给定一棵树时:

_{(来源:ernet.in)}

函数返回 [[1];[2;3];[4;5;6;7];[8;9]]。

let levels tree =
  let aux x fl fp = 
    fun l ->
    match l with
    | [] -> [x] :: (fl (fp []))
    | h :: t -> (x :: h) :: (fl (fp t))
  in fold_tree aux (fun x -> x) tree [];;

显然它有效，但我无法全神贯注。谁能用简单的术语解释发生了什么？为什么这个功能有效？

Answer 1

如何合并两个子树的两个层列表并获得错误树的层列表？假设你有这棵树

   a
  / \
 x   y

其中 x 和 y 是任意树，它们的层列表为 [[x00,x01,...],[x10,x11 ,...],...] 和 [[y00,y01,...],[y10,y11,...],...]。

新树的层列表将是[[a],[x00,x01,...]++[y00,y01,...],[x10,x11,...]++[y10,y11,...],...]。这个函数是怎么构建的？

让我们看看这个定义

let rec fold_tree f a t = ...

并查看我们在 levels 的定义中传递给 fold_tree 的参数类型。

... in fold_tree aux (fun x -> x) tree []

所以第一个参数 aux 是某种长而复杂的函数。我们稍后会返回。

第二个参数也是一个函数——恒等函数。这意味着 fold_tree 也将返回一个函数，因为 fold_tree 总是返回与其第二个参数相同类型的值。我们将讨论应用于这组参数的函数 fold_tree 获取一个层列表，并将给定树的层添加到其中。

第三个参数是我们的树。

等等，第四个参数是什么？ fold_tree 只应该得到树？是的，但由于它返回一个函数(见上文)，该函数将应用于第四个参数，即空列表。

让我们回到aux。此 aux 函数接受三个参数。一个是树的元素，另外两个是子树折叠的结果，即 fold_tree 返回的任何内容。在我们的例子中，这两件事又是函数。

所以 aux 得到一个树元素和两个函数，并返回另一个函数。那是哪个函数？它需要一个层列表，并向其中添加给定树的层。它是怎么做到的？它将树的根添加到列表的第一个元素(顶层)，然后通过调用将右子树的层添加到列表的尾部(顶层以下的所有层) right 函数，然后通过调用 left 函数 将左子树的层添加到结果中。或者，如果传入列表为空，则通过将上述步骤应用于空列表，它只是重新列出图层。