理解递归中的堆栈展开（树遍历）
我正在编写一个遍历二叉搜索树的程序。这是我的代码：
Main.java
public class Main { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); binaryTree.add(50); binaryTree.add(40); binaryTree.add(39); binaryTree.add(42); binaryTree.add(41); binaryTree.add(43); binaryTree.add(55); binaryTree.add(65); binaryTree.add(60); binaryTree.inOrderTraversal(binaryTree.root); } } Node.java
public class Node { int data; Node left; Node right; Node parent; public Node(int d) { data = d; left = null; right = null; } }
BinaryTree.java
public class BinaryTree { Node root = null; public void add(int d) { Node newNode = new Node(d); if(root!=null) { Node futureParent = root; while(true) { if(newNode.data < futureParent.data) //going left { if(futureParent.left == null) { futureParent.left = newNode; newNode.parent = futureParent; break; } futureParent = futureParent.left; } else { if(futureParent.right == null) { futureParent.right = newNode; newNode.parent = futureParent; break; } futureParent = futureParent.right; } } } else { root = newNode; } } public void inOrderTraversal(Node node) { if(node!=null) { inOrderTraversal(node.left); System.out.println(node.data); inOrderTraversal(node.right); } } }
我完全了解添加过程，但我无法理解遍历。 现在，我正在使用的树，以便更好地参考：
inOrderTraversal()函数中的第一个语句访问50,40然后39，最后命中null，使if条件为false，之后打印39并搜索右子。此后第一个语句停止执行，堆栈展开第二和第三个语句（ inOrderTraversal(node.right)和print(node.data) ）导致打印40并遍历到41，这是我不理解的部分，即编译器如何重新启动语句1（ inOrderTraversal(node.left) ）一旦堆栈中有新鲜东西就停止执行。
你的代码不能正常工作，它将永远遍历节点39.方法inOrderTraversal（）确实将转到左边节点，但由于while而将永远循环。 每个堆栈框架都有自己的变量副本。 输入方法时，变量节点获取作为参数传递的对象引用的副本。
考虑递归的一种方法是类似于使用while循环，但是有一个if，而不是while。 以下是该方法的外观：
public void inOrderTraversal(Node node) { if (node != null) { inOrderTraversal(node.left); System.out.println(node.data); inOrderTraversal(node.right); } }
遍历树时，首先要打印较小的值，该值存储在最左边的节点中，因此使用inOrderTraversal(node.left); 如果。 当您到达空节点时，这意味着它的父节点是最左侧的节点，因此您将其打印出来。 之后，转到右侧节点并重复此过程。 这就像在较小的子树中分割树，直到你不能再分割它们并打印它们的值。
每次调用方法（递归与否）时，都会分配一个新的堆栈帧（推送到堆栈），并在方法完成后，删除堆栈（弹出），释放垃圾回收空间。 这些堆栈帧只是局部变量存在的临时空间。 对象成员变量位于另一个称为堆的地方，它的生命周期比堆栈长。
JVM处理这些空间的分配，垃圾收集器根据对象/变量的生命周期释放它们。 根据他们的生活多少，有几代人（这就是他们所谓的）。 一切都从伊甸园（年轻）一代开始，如果垃圾收集器由于它们还活着而没有收回空间，它们会被转移到幸存者一代，之后如果它们仍未被收集，它们会移动到最后一个，终身一代。 物体存在的时间越长，GC检查它们就越少。 这意味着虽然伊甸园中的物体收集得非常快，但其他几代人的检查时间并不常见。 还有另一个称为永久生成（permgen）的空间，其中常量用于生存（如字符串文字）和存储类的位置。
通过考虑经典的递归示例，factorial，您可以更清楚地了解递归和堆栈。
int factorial(x) { int result; if(x==1) result = 1; else result = x * factorial(x - 1); return result; }
（我使用result变量，以便在手动单步执行代码时更容易标记位置）
使用纸张手动执行factorial(5)的执行。
首先将function写在一张纸上，用5代替’x’。然后仔细阅读，当你进行function调用时，在你的执行点放一个铅笔标记，然后为你的纸张取一张新纸。新function调用。
每次执行此操作时，将新纸放在上一张纸的顶部。 从字面上看，这是一叠纸 ，它准确地代表了一个计算机堆栈 。 每张纸都是一个堆栈条目 ，它记录了您在代码中的位置，以及创建它时局部变量的值。
重要的是要理解这对递归函数调用并不特殊。 所有函数调用都以这种方式创建堆栈条目。
程序执行无法浏览堆栈。 只能访问顶层纸张 – 后进先出 （LIFO）。 当你得到factorial(1) ，它不会再次召唤自己，而你会return 。 发生这种情况时，丢弃顶部纸张，将返回值写入新的顶层，然后从放置铅笔标记的位置继续单步执行顶层的function。
这样继续，最后你丢弃最后一张。 这意味着您的程序已经完成，并且您有最终结果。
顺便说一句，如果您的代码出现问题，那么在任何情况下，该function都不会自行调用，您将耗尽纸张（或者您的纸叠将达到最高限度） – 这就是堆栈溢出网站被命名。 堆栈大于强加的最大值，运行时拒绝再次调用该函数（在Java中，通过抛出exception）。 您可能会在编程生涯中遇到这种情况 – 常见原因是编码严重的停止条件，或者循环数据结构。
通过上面的实现， factorial(0)可能会导致堆栈溢出。 你能明白为什么吗？
这就是所有传统计算机程序的运行方式。 您将一个项目放在堆栈上（在C和Java中，这是main() ）。 每次进行函数调用时，堆栈都会增长，每次函数完成时，堆栈都会缩小。 堆栈增长和缩小，直到它最终缩小为零，此时程序完成。
对于像你这样的程序，在同一个函数中有两个递归调用，没有什么不同。 这是一个很好的练习，用一张纸手动完成一个小的二叉树搜索，就像我们使用factorial()看它工作一样。
在调试器中暂停Java代码以查看当前堆栈的状态也是Thread.dumpStack() – 或者如果你不能这样做（学习很快使用调试器！）在代码中的某处放置一个Thread.dumpStack()看看它输出了什么。
首先， inOrderTraversal的while语句是错误的。 while循环中的所有语句都不会修改变量node所以如果它是null ，它将永远是，如果不是，它将永远不会。 将其更改为if 。
有了这个，看看递归的方法通常是归纳。 我要求以下归纳假设：
给定以
node根的树T，inOrderTraversal(node)打印T的有序遍历并返回。
我们可以通过归纳表明这确实发生了。 简单的情况是node == null 。 在这种情况下， inOrderTraversal打印任何内容并直接返回，这与假设一致。
现在，假设我们传递了一个非空树。 通过归纳， inOrderTraversal(node.left)打印左子树并返回。 然后，打印node.data 。 最后，再次通过归纳， inOrderTraversal(node.right)打印出正确的子树并返回。 请注意，到目前为止，当前树是按顺序遍历打印的。 由于我将while改为a， if该方法返回，从而满足归纳假设。
这回答了你的问题了吗？