通过二叉树进行追踪
Tracing through a Binary Tree
我有以下二叉树
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 (top node), not null, Root.left(5) - 回到函数
Root = 5, Not null, Root.left(1) - 返回函数
Root = 1，不为空，Root.left(null)，继续，Root.right(null)
打印 1
现在这是我感到困惑的地方，Root = 1 在这一点上，我不明白如何回到 5 然后转到正确的节点逻辑。另外，当我回到5时，我在哪里检查1是否已经被访问过？
我很困惑。
感谢您的帮助。
是的，所以当您位于根 1（叶子）时，它将 return 到调用它的节点 (5)。
因为在 "Root 5"，它刚刚完成调用 Postorder(root.left);（刚刚 return 从打印 1 编辑），下一行将 运行 并调用 Postorder(root.right);.
这将调用 root = 4。不为空，root.left(null)，继续，root.right(null)，继续，现在 print 4。
现在我们跳回到调用节点，root = 5。现在它已经调用了Root.left(1);和Root.right(4);。所以现在它要 print 5。
它现在将 return 到调用节点 - 在本例中是整个树的根，root = 3 现在它将以类似的方式遍历右侧。
Understanding and visualizing recursion也许再见这对你有帮助，因为你对递归的理解是错误的。你需要记住所有的函数调用。
递归很简单。您需要做的就是不断地将 Binary Search Tree 分成左子树和右子树。
您可能还想考虑为您的变量创建 getters 以更好地封装您的 Node class。
后序函数
public void Postorder( Node root )
{
if( root == null )
return;
// Output the left tree.
if( root.left != null )
Postorder( root.left );
// Output the current node.
System.out.print( root.data + " " );
// Output the right tree.
if( root.right != null )
Postorder( root.right );
}
也许图片会有所帮助。我也发现递归很困难，而且我发现图片很有用。在单独的 window 中打开图表并在旁边进行解释可能会很好。
首先，递归使用称为堆栈的东西。这是您在图中看到的一堆四个矩形。例如，最后有两个空栈。假设函数 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 个部分，请告诉我。之后会有点乏味。希望这个视觉效果有所帮助。
我有以下二叉树
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 (top node), not null, Root.left(5) - 回到函数
Root = 5, Not null, Root.left(1) - 返回函数
Root = 1，不为空，Root.left(null)，继续，Root.right(null)
打印 1
现在这是我感到困惑的地方，Root = 1 在这一点上，我不明白如何回到 5 然后转到正确的节点逻辑。另外，当我回到5时，我在哪里检查1是否已经被访问过？
我很困惑。
感谢您的帮助。
是的，所以当您位于根 1（叶子）时，它将 return 到调用它的节点 (5)。
因为在 "Root 5"，它刚刚完成调用 Postorder(root.left);（刚刚 return 从打印 1 编辑），下一行将 运行 并调用 Postorder(root.right);.
这将调用 root = 4。不为空，root.left(null)，继续，root.right(null)，继续，现在 print 4。
现在我们跳回到调用节点，root = 5。现在它已经调用了Root.left(1);和Root.right(4);。所以现在它要 print 5。
它现在将 return 到调用节点 - 在本例中是整个树的根，root = 3 现在它将以类似的方式遍历右侧。
Understanding and visualizing recursion也许再见这对你有帮助，因为你对递归的理解是错误的。你需要记住所有的函数调用。
递归很简单。您需要做的就是不断地将 Binary Search Tree 分成左子树和右子树。
您可能还想考虑为您的变量创建 getters 以更好地封装您的 Node class。
后序函数
public void Postorder( Node root )
{
if( root == null )
return;
// Output the left tree.
if( root.left != null )
Postorder( root.left );
// Output the current node.
System.out.print( root.data + " " );
// Output the right tree.
if( root.right != null )
Postorder( root.right );
}
也许图片会有所帮助。我也发现递归很困难，而且我发现图片很有用。在单独的 window 中打开图表并在旁边进行解释可能会很好。
首先，递归使用称为堆栈的东西。这是您在图中看到的一堆四个矩形。例如，最后有两个空栈。假设函数 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 个部分，请告诉我。之后会有点乏味。希望这个视觉效果有所帮助。