时间戳

首页 > 解决方案 > 有人可以向我解释一下树遍历在这里做什么吗？

algorithm - 有人可以向我解释一下树遍历在这里做什么吗？

问题描述

我很难理解 tree_traverse 函数及其作用，有人可以解释一下。

（Peek and pop 只是来自我制作的堆栈实现。）

type 'a tree = Leaf | Branch of ('a tree * 'a * 'a tree);;

let rec tree_traverse (t,mem,prim,seco) = match t with
  | Leaf ->
    if is_empty mem
    then []
    else tree_traverse (peek mem, pop mem, prim, seco)
  | Branch (l,nd,r) ->
    let mem1 = add (prim(l,r),mem) in
    let mem2 = add (seco(l,r), mem1) in
    nd :: tree_traverse (peek mem2, pop mem2, prim, seco)

其中一棵树的例子是

  let t = Branch (Branch(Branch(Leaf,1,Leaf), 2, Leaf), 3,
            Branch (Branch(Leaf,5,Leaf), 6, Branch(Leaf,7,Leaf)))

标签： algorithmocaml

解决方案

这个函数实现了某种工作列表算法，它以某种顺序返回一个节点列表，这取决于prim和seco函数的实现，以及add和pop。

在递归期间既不改变参数prim也不seco改变参数，因此可以从参数列表中删除。如果我们假设以下实现

 let add (x,xs) = x :: xs
 let pop (x::xs) = xs
 let peek (x::xs) = x
 let prim (x,y) = x
 let seco (x,y) = y
 let is_empty = function [] -> true | _ -> false

然后该tree_traverse函数将按深度优先顺序返回节点列表。

给定您的示例并将实现修复为上述指定的函数，我们现在可以跟踪函数的执行： 

tree_traverse Branch (Branch(Branch(Leaf,1,Leaf), 2, Leaf), 3,
        Branch (Branch(Leaf,5,Leaf), 6, Branch(Leaf,7,Leaf)))

与案例不匹配，Leaf所以我们转到第二种情况并将其解构为

 | Branch (l,nd,r)) ->
    (* l is bound to Branch (Branch(Leaf,1,Leaf), 2, Leaf) *)
    (* nd is bound to 3 *)
    (* r is bound to Branch (Branch(Leaf,5,Leaf), 6, Branch(Leaf,7,Leaf)) *)
    let mem1 = add (prim(l,r),mem) in
    let mem2 = add (seco(l,r), mem1) in
    nd :: tree_traverse (peek mem2, pop mem2, prim, seco)

我们将左子分支压入l第一个堆栈mem1，并将左右子分支压入堆栈mem2。然后我们将结果添加到结果之前，并在丢弃它的同时3递归到堆栈的顶部。mem2

在下一步中，我们在第二个堆栈的顶部进行匹配，其中包含右分支，即Branch (Branch(Leaf,5,Leaf), 6, Branch(Leaf,7,Leaf))，我们再次降落到第二种情况， Branch(Leaf,5,Leaf)绑定到l变量，然后Branch(Leaf,7,Leaf)到r。我们添加6到结果中，然后 pushl然后 push 并立即弹出r并递归到它。

在递归的第三步，我们用 调用Branch(Leaf,7,Leaf)，我们添加7到我们的结果，然后左右推入Leaf我们的堆栈。

第四步，我们查看Leaf节点，最后进入第一种情况，我们查看堆栈，如果它不为空，则递归到顶部。在我们的例子中，堆栈包含我们的兄弟 left Leaf，然后是父节点的左兄弟，等等。

您可以使用 OCaml 顶层执行相同的操作，例如，

#trace tree_traverse;;
tree_traverse (t,[],prim,seco);;

使用我上面提供的辅助函数的定义。

推荐阅读