Rekursive Preorder Traversallauf bis Stapelüberläufe, (BST) in JAVA

Question

Ich implementiere einfache binäre Suchbaum in Java mit Einfügen und Vorbestellmethoden. Ich stoße in die unendliche Preorder-Ausführung, bis Stackoverflows auftreten.

Hier ist die Node-Klasse ist:

public class Node { 
private Node right, left; 
private int data; 

public Node(Node right, Node left, int data) { 
    super(); 
    this.right = right; 
    this.left = left; 
    this.data = data; 
} 

public Node() { 
    super(); 
    this.right = this.left = null; 
    this.data = 0; 
} 

public Node getRight() { 
    return right; 
} 

public void setRight(Node n) { 

    this.right = n; 
} 

public Node getLeft() { 
    return left; 
} 

public void setLeft(Node n) { 
    this.left = n; 
} 

public int getData() { 
    return data; 
} 

public void setData(int data) { 
    this.data = data; 
} 

} 

Hier ist die BinarySearchTree Klasse:

public class BinarySearchTree { 

private Node root; 

public BinarySearchTree() { 
    root = null; 
} 

public Node insert(int data) { 
    root = insertInto(root, data); 
    return root; 
} 

private Node insertInto(Node node, int data) { 

    if (node == null) { 
     Node temp = new Node(); 
     temp.setData(data); 
     return temp; 
    } else if (data < node.getData()) { 

     node.setLeft(insertInto(node.getLeft(), data)); 

    } else if (data > node.getData()) { 

     node.setRight(insertInto(node.getRight(), data)); 

    } 

    return root; 
} 

public void preorder() { 
    getPreorder(root); 
} 

private void getPreorder(Node root) { 
    if (root == null) 
     return; 
    System.out.println(root); 
    getPreorder(root.getLeft()); 
    getPreorder(root.getRight()); 
} 
} 

Hier ist die Hauptklasse:

public class BstMain { 

public static void main(String args[]) 
{ 
    BinarySearchTree bst = new BinarySearchTree(); 

    bst.insert(10); 

    bst.insert(9); 

    bst.insert(15); 

    bst.insert(8); 
    bst.insert(20); 
    bst.preorder(); 

} 
} 

Hier ist die Ausgabe:

Node [data=10] 
Node [data=10] 
Node [data=10] 
Node [data=10] 
Node [data=10] 
Node [data=10] 
Node [data=10] 
Node [data=10] 
Exception in thread "main" java.lang.StackOverflowError 
at sun.nio.cs.SingleByte.withResult(Unknown Source) 
at sun.nio.cs.SingleByte.access$000(Unknown Source) 
at sun.nio.cs.SingleByte$Encoder.encodeArrayLoop(Unknown Source) 
at sun.nio.cs.SingleByte$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.println(Unknown Source) 
at bsTree.BinarySearchTree.getPreorder(BinarySearchTree.java:42) 
at bsTree.BinarySearchTree.getPreorder(BinarySearchTree.java:43) 
at bsTree.BinarySearchTree.getPreorder(BinarySearchTree.java:43) 
at bsTree.BinarySearchTree.getPreorder(BinarySearchTree.java:43) 

Ich denke, es ist etwas falsch mit Einfügelogik, kann nicht herausfinden, was es ist.

Answer 1

Das Problem ist in insertInto(...):

} else if (data < node.getData()) { 

    node.setLeft(insertInto(node.getLeft(), data)); 

} else if (data > node.getData()) { 

    node.setRight(insertInto(node.getRight(), data)); 

} 

return root; 

In jedem dieser beiden Fälle, Sie am Ende der linken/rechten Kind auf den Wurzelknoten einstellen, so dass Sie einen Zyklus erstellen. Das verursacht die unendliche Rekursion.