java - 通过二叉树进行追踪

Question

我有以下二叉树

    3
   /  \
  5     2
 / \    /
1   4   6

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

我有以下代码，它的作用是打印后序中的节点。 所以答案是 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(顶部节点)，不为空，Root.left(5) - 返回到函数

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

Root = 1，不为空，Root.left(null)，继续，Root.right(null)

打印1

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

我很困惑。

感谢您的帮助。

Answer 1

也许图片会有所帮助。我发现递归也很困难，而且我发现图片很有用。在单独的窗口中打开图表并在侧面提供说明可能会很好。

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

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

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

1

因此，最初，main 运行及其内容被添加到堆栈底部，如我们在第 1 部分中看到的那样。

1->2

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

2->3

现在，我们正在执行 Postorder(3)，并到达函数调用 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 行停下来，然后跳到执行另一个函数。好吧，我们现在可以转到 Postorder(5) 的第 2 行。这对应于第 5 部分。

5->6

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

...

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