2

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

主.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);
} 
}

节点.java

 public class Node {
 int data;
 Node left;
 Node right;
 Node parent;


public Node(int d)
{
data = d;
left = null;
right = null;
}
}

二叉树.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 并搜索右孩子。在此之后第一条语句停止执行并且堆栈展开第二个和第三个导致打印 40 并遍历到 41 的语句（inOrderTraversal(node.right)和），这是我不明白的部分，即一旦堆栈中有新的东西，编译器停止执行后如何重新启动语句 1（）。print(node.data)inOrderTraversal(node.left)

4

3 回答 3

3

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

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

（我使用该result变量使手动单步执行代码时更容易标记位置）

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

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

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

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

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

像这样继续下去，最终你会丢弃最后一张纸。这意味着您的程序已经完成并且您有一个最终结果。

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

使用上面的实现，factorial(0)可能会导致堆栈溢出。你能看出为什么吗？

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

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

在调试器中暂停 Java 代码以查看当前堆栈的状态也很有指导意义——或者如果你不能这样做（尽快学会使用调试器！）Thread.dumpStack()在代码中的某个位置放置以查看它的输出.

于 2014-02-27T09:05:17.320 回答
1

您的代码不能按原样工作，它将永远在节点 39 上迭代。 inOrderTraversal() 方法确实会转到左侧节点，但由于一段时间，它将永远在它上面循环。每个堆栈帧都有自己的变量副本。进入方法时，变量节点获取作为参数传递的对象引用的副本。

考虑递归的一种方法是类似于使用 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);获取 if。当你到达一个空节点时，这意味着它的父节点是最左边的节点，所以你打印它。之后，您转到正确的节点并重复该过程。这就像将树拆分为较小的子树，直到您无法再拆分它们并打印它们的值。

每次调用方法（递归或非递归）时，都会分配一个新的堆栈帧（压入堆栈），在方法完成后，堆栈会被移除（弹出），从而为垃圾回收释放空间。这些堆栈帧只是局部变量所在的临时空间。对象成员变量存在于另一个称为堆的地方，它的生命周期比堆栈长。

JVM 处理这些空间的分配，垃圾收集器根据对象/变量的生命周期释放它们。根据他们的寿命，有几代人（这就是他们所说的）。一切都从伊甸园（年轻）一代开始，如果垃圾收集器因为它们还活着而没有回收空间，它们就会被移到幸存者代，如果它们仍然没有被收集，它们就会移到最后一个，终身的一代。对象存活的时间越长，GC 对其进行检查的次数就越少。这意味着虽然伊甸园中的对象被收集得非常快，但其余代的检查并不那么频繁。还有另一个称为永久代 (permgen) 的空间，用于存在常量（如字符串文字）和存储类的地方。

于 2014-02-27T08:15:58.477 回答
0

首先，里面的while说法inOrderTraversal是错误的。循环中的任何语句都不会while修改变量node，因此如果它是null，它将永远是，如果不是，它永远不会。将其更改为if.

有了这个，查看递归的方法通常是归纳。我主张以下归纳假设：

给定一棵以 为T根的树node，inOrderTraversal(node)打印 的中序遍历T并返回。

我们可以通过归纳证明这确实发生了。简单的情况是 when node == null。在这种情况下，inOrderTraversal什么也不打印，直接返回，这符合假设。

现在，假设我们传递一棵非空树。通过归纳，inOrderTraversal(node.left)打印左子树并返回。然后，node.data被打印。最后，再次通过归纳，inOrderTraversal(node.right)打印右子树并返回。请注意，到目前为止，当前树是按顺序遍历打印的。由于我将 更改为while方法if返回，从而满足归纳假设。

这回答了你的问题了吗？

于 2014-02-27T07:54:54.927 回答