java - 通过二叉树进行追踪

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() 在 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 个部分，请告诉我。之后会有点乏味。希望这个视觉效果有所帮助。