java - 了解递归中的堆栈展开(树遍历)

Question

我正在编写一个程序来遍历二叉搜索树。这是我的代码:

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))。

Answer 1

通过思考经典的递归示例阶乘，您可以更清楚地了解递归和堆栈。

int factorial(x) {
   int result;
   if(x==1) 
       result = 1;
   else
       result = x * factorial(x - 1);
   return result;
 }

(我使用 result 变量以便在手动单步执行代码时更容易标记位置)

运行 factorial(5) 的执行手动，使用纸张。

首先将函数写在一张纸上，将“x”替换为 5。然后通读它，当遇到函数调用时，在执行点处用铅笔标记，并获得一张新纸新函数调用的论文。

每次执行此操作时，请将新纸放在前一张纸的上面。从字面上看，这是一叠纸，它准确地代表了计算机的堆栈。每张纸都是一个堆栈条目，它记录了您在代码中的位置，以及创建代码时局部变量的值。

重要的是要理解这对于递归函数调用来说并不特殊。所有函数调用都以这种方式创建堆栈条目。

程序执行无法浏览堆栈。只能访问最上面的一张纸——后进先出 (LIFO)。当您到达factorial(1)时，它不会再次调用自己，然后您会看到 return 。当发生这种情况时，丢弃最上面的一张纸，将返回值写入新的顶层，然后从您放置铅笔标记的位置继续单步执行顶层的函数。

如此下去，最终你会丢弃最后一张纸。这意味着您的程序已经完成并且您得到了最终结果。

顺便说一句，如果你的代码有问题，比如函数不调用自身，你就会用完纸(或者你的纸堆会到达天花板)——这就是堆栈溢出，该网站由此命名。堆栈变得大于规定的最大值，并且运行时拒绝再次调用该函数(在 Java 中，通过抛出异常)。您可能会在编程生涯中遇到这种情况 - 常见原因是编码错误的停止条件，或者循环数据结构。

通过上述实现，factorial(0)可能会导致堆栈溢出。你能明白为什么吗？

这就是所有传统计算机程序的运行方式。您将一项放在堆栈上(在 C 和 Java 中，即 main() )。每次进行函数调用时，堆栈都会增长，而每次函数完成时，堆栈都会缩小。堆栈不断增大和缩小，直到最终缩小到零，此时程序就完成了。

对于像您这样的程序，在同一函数中进行两次递归调用，没有什么不同。使用纸张手动运行小型二叉树搜索是一个很好的练习，就像我们对 factorial() 所做的那样。看看它的工作原理。

在调试器中暂停 Java 代码以查看当前堆栈的状态也很有帮助——或者如果您无法做到这一点(尽快学习使用调试器!)，则输入 Thread.dumpStack()在代码中的某个位置查看它的输出。