通过二叉树进行跟踪

Question

我有下面的二叉树

    3
   /  \
  5     2
 / \    /
1   4   6

我的星期是递归，所以请忍耐我，我需要你的帮助追溯通过它得到正确的。

我有下面的代码，它所做的是按Post顺序打印节点。所以答案是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（顶部节点）,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()调用postorder(3)时，它还没有终止。因此，在另一个堆栈帧中，我们添加postorder(3)函数调用的内容。您可以在第2部分中看到这一点。黄色箭头记住了我们在执行另一个函数之前在每个堆栈帧中停止的位置。

现在，我们正在执行postorder(3)并到达函数调用postorder(5)。但是postorder(3)还没有运行完，所以在另一个堆栈帧中，我们不得不添加postorder(5)的内容。您可以在第3部分中看到这一点。

现在我们正在执行postorder(5)。我们到达函数调用postorder(1)。但是postorder(5)还没有运行完，所以在另一个stackframe中，我们不得不添加postorder(1)的内容。为了简单起见，由于1没有子节点，我们将说postorder(1)等同于print(1)。这与第4部分相对应。

现在，在第4部分中，Print(1)执行，postorder(1)终止。当postorder(1)终止时，可以将其从堆栈中删除。此外，由于postorder(1)已完成，我们可以继续执行postorder(5)。黄色箭头告诉我们，在跳过执行另一个函数之前，我们在postorder(5)的第1行停止了操作。好了，我们现在可以转到postorder(5)的第2行。这与第5部分相对应。

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

...

从那时起，这个想法几乎是一样的。让我知道如果你还想让我一步通过剩下的8个部分。之后就有点乏味了。希望这种视觉效果能有所帮助。