跟踪二叉树

Question

我有以下二叉树

    3
   /  \
  5     2
 / \    /
1   4   6

我的周末是递归的，所以请耐心等待，我需要你的帮助来追踪它以使其正确。

我有以下代码，它的作用是在 Post Order 中打印节点。所以答案是 1 4 5 6 2 3

void Postorder(Node root) {

if(root == null){
    return;
}

Postorder(root.left);
Postorder(root.right);
System.out.print(root.data + " ");
}

让我们追踪：

Root = 3 (top node), not null, Root.left(5) - 回到函数

Root = 5, Not null, Root.left(1) - 回到函数

Root = 1, Not null, Root.left(null), continue, Root.right(null)

打印 1

现在这是我感到困惑的地方，此时Root = 1，我不知道如何回到 5 然后转到逻辑中的正确节点。另外，当我回到 5 时，我在哪里检查 1 是否被访问过？

我很迷惑。

谢谢你的帮助。

Answer 1

也许这张照片会有所帮助。我发现递归也很困难，而且我发现图片很有用。在单独的窗口中打开图表并在旁边有解释可能会很好。

首先，递归使用称为堆栈的东西。这是你在图中看到的一堆四个矩形。例如，最后有两个空栈。假设一个函数在终止之前A()调用了一个函数。然后需要发生的是我们在中途执行，然后执行，然后返回并完成执行。但是当我们去执行时，我们需要记住我们所处的位置。因此，我们需要在堆栈中的各个矩形中存储关于和的信息。这样，在我们完成执行之后，我们就知道我们在哪里停下来并可以完成该函数。B()AA()B()A()B()A()A()B()B()A()

因此，如果我们使用堆栈图逐步执行递归，也许会有所帮助。还假设我们有这个：

public static void main( String[] args ) {
    Postorder(3);
}

1

所以最初，主运行及其内容被添加到堆栈的底部，如我们在第 1 部分中看到的。

1->2

但是当main()调用 时Postorder(3)，它还没有终止。因此，在另一个堆栈帧中，我们添加了Postorder(3)函数调用的内容。您可以在第 2 部分中看到这一点。黄色箭头记住我们在执行另一个函数之前在每个堆栈帧中离开的位置。

2->3

现在，我们正在执行Postorder(3)并到达函数 call Postorder(5)。但是Postorder(3)还没有跑完，所以在另一个栈帧中，我们要添加Postorder(5). 您可以在第 3 部分中看到这一点。

3->4

现在我们正在执行Postorder(5). 我们到达了函数调用Postorder(1)。但是Postorder(5)还没有跑完，所以在另一个stackframe中，我们要添加Postorder(1). 为简单起见，由于 1 没有子节点，我们会说它Postorder(1)等价于Print(1)。这对应于第 4 部分。

4->5

现在，在第 4 部分中，Print(1) 执行并Postorder(1)终止。当Postorder(1)终止时，它可以从堆栈中移除。此外，既然Postorder(1)完成了，我们可以继续执行Postorder(5). 黄色箭头告诉我们，Postorder(5)在跳到执行另一个函数之前，我们在第 1 行离开了。好吧，我们现在可以转到 的第 2 行Postorder(5)。这对应于第 5 部分。

5->6

第 2 行Postorder(5)是命令Postorder(4)。由于Postorder(5)尚未完成执行，我们必须将 的内容添加Postorder(4)到另一个堆栈帧中。这对应于第 6 部分。

...

从那时起，这几乎是相同的想法。如果您仍然希望我逐步完成剩余的 8 个部分，请告诉我。之后就有点乏味了。希望这个视觉有帮助。