Исключение переполнения стека двоичного дерева при обходе inorder - PullRequest
Новая
       40

Исключение переполнения стека двоичного дерева при обходе inorder

0 голосов
/ 29 декабря 2018

Я изучаю структуры данных и наткнулся на ПБМ, который я не могу решить.Кто-нибудь может помочь здесь?

Я создал TreeNode Класс.В том же пакете я создал другой класс.этот класс имеет два метода.Один выполняет inorder обход, и есть другой метод (создание нового двоичного дерева из существующего).Я назвал 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 будет работать нормально.Я не могу понять, почему это так?Может кто-нибудь помочь, пожалуйста?

Спасибо!

1 Ответ

0 голосов
/ 29 декабря 2018

В вашем методе orderTraversal вы изменяете свое дерево в строке 

prev.right = curr1;

Это ваша ошибка.Я действительно не знаю, что вы собираетесь делать там, но вы не должны изменять свое дерево при обходе дерева.

Вы сказали:

второй метод относится только кпеременные экземпляра

Но когда вы делаете prev = curr1, ваша переменная экземпляра prev указывает на узел в дереве.Затем, когда вы делаете prev.right = curr1, вы изменяете узел, на который указывает prev.

Поскольку вы модифицируете свое дерево, вы создаете циклическую ссылку.Узел 3 имеет узел 9 в качестве своего левого потомка, но узел 9 снова имеет 3 (своего собственного родителя) в качестве своего левого потомка.Это больше не дерево, и поэтому во второй раз вы набираете бесконечное количество вызовов inOrder1, что заканчивается StackOverflowError.

Кстати, это можно легко увидеть, используяотладчик, я предлагаю вам взглянуть на эту страницу .

...