java - JAVA 中的递归前序遍历运行直至堆栈溢出(BST)

Question

我正在使用插入和预排序方法在java中实现简单的二叉搜索树。我遇到无限预购执行，直到堆栈溢出。

这是 Node 类:

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;
}

}

这是 BinarySearchTree 类:

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());
}
}

这是主类:

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();

}
}

这是输出:

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)

我认为插入逻辑有问题，无法弄清楚它是什么。

Answer 1

问题出在 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;

在这两种情况中的任何一种情况下，您最终都会将左/右子节点设置为根节点，因此您正在创建一个循环。这就是导致无限递归的原因。