java - 二叉树中序遍历时抛出堆栈溢出异常

Question

我正在学习数据结构，遇到了一个无法解决的 pbm。有人可以帮忙吗？

我创建了一个TreeNode类。在同一个包中我创建了另一个类。这个类有两个方法。一种是中序遍历，还有另一种方法(从现有的二叉树中创建一个新的二叉树)。我调用了 inorder 遍历，效果很好。但是，如果我在其他方法之后调用 inorder 遍历方法，则会出现异常。

另一个方法创建一个新的二叉树，但它独立于inorder遍历方法

public class TreeNode {
     public int val;
     public TreeNode left;
     public TreeNode right;
     TreeNode(int x) { val = x; }
}

In the same package I created another class.

package BST;
public class Check {
    TreeNode curr;
    TreeNode prev;

public void orderTraversal( TreeNode curr1) {

        if(curr1 == null)
            return;

        orderTraversal(curr1.left);

        if(curr == null ) {
            curr = curr1;
            prev = curr1;
        }
        else {
            prev.right = curr1;
            prev = curr1;
        }

        orderTraversal(curr1.right);
    }

    public static void main(String[] args) {
            // TODO Auto-gene`enter code here`rated method stub

        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.right = new TreeNode(15);

        Check check = new Check();  
        check.inOrder1(root);
        check.orderTraversal(root);
        check.inOrder1(root);
    }
    public  void inOrder1(TreeNode root) {
        if(root !=  null) {
            inOrder1(root.left); 
            System.out.printf("%d ",root.val);
            inOrder1(root.right);
        }

    }

}

When running the program , I am getting an exception in the method in the second call of inOrder1 . 

at sun.nio.cs.UTF_8.updatePositions(Unknown Source)
    at sun.nio.cs.UTF_8.access$200(Unknown Source)
    at sun.nio.cs.UTF_8$Encoder.encodeArrayLoop(Unknown Source)
    at sun.nio.cs.UTF_8$Encoder.encodeLoop(Unknown Source)
    at java.nio.charset.CharsetEncoder.encode(Unknown Source)
    at sun.nio.cs.StreamEncoder.implWrite(Unknown Source)
    at sun.nio.cs.StreamEncoder.write(Unknown Source)
    at java.io.OutputStreamWriter.write(Unknown Source)
    at java.io.BufferedWriter.flushBuffer(Unknown Source)
    at java.io.PrintStream.write(Unknown Source)
    at java.io.PrintStream.print(Unknown Source)
    at java.io.PrintStream.append(Unknown Source)

我知道java是按值传递的。第二种方法仅引用实例变量。如果我注释掉 check.orderTraversal(root) ，则对 InOrder1 的第二次调用工作正常。我不明白为什么会这样？有人可以帮忙吗？

谢谢!

Answer 1

在您的方法 orderTraversal 中，您正在修改行中的树

prev.right = curr1;

这是你的错误。我真的不知道你打算在那里做什么，但你不应该在树遍历中修改你的树。

你说

the second method is referring only the instance variables

但是当您执行 prev = curr1 时，您的实例变量 prev 指向树中的一个节点。然后，当您执行 prev.right = curr1 时，您会修改 prev 指向的节点。

因为您修改了树，所以创建了循环引用。节点 3 将节点 9 作为其左子节点，但节点 9 又将 3(其自己的父节点)作为其左子节点。这不再是一棵树，这就是为什么当您第二次调用 inOrder1 时会有无数次调用，最终以 StackOverflowError 结束。

顺便说一下，使用调试器可以很容易地看到这一点，我建议你看看this page .