java 中的 BST 实现出现错误

Question

我正在尝试实现一个简单的 BST，然后按顺序打印出元素。我似乎得到了错误的输出，甚至运行调试器也无法真正理解出了什么问题。这是我使用 add 和 inorder 方法实现的 BST。

public class BST {
    private Node root;

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

        public Node(int data){
            this.data = data;
        }
    }

    public BST(int item){
        root = new Node(item);
    }

    public void add(int item){
        root = add(item, root);
    }

    private Node add(int item, Node curr){

        if(curr == null){
            curr = new Node(item);
            return curr;
        }
        if(item < curr.data) curr.left = add(item, curr.left);
        if(item > curr.data) curr.right = add(item, curr.left);
        return curr;

    }
    public void inorder(){

        inorder(root);
    }

    private void inorder(Node curr){
        if(curr == null) return;
        inorder(curr.left);
        System.out.print(curr.data + " ");
        inorder(curr.right);
    }

这是调用客户端。

public class Solution {

    public static void main(String[] args) {

        BST bst = new BST(12);
        //bst.add(12);
        bst.add(7);
        bst.add(16);
        bst.add(3);
        bst.add(9);
        bst.add(13);
        bst.add(19);
        bst.inorder();
        //bst.printLevelByLevel();
    }
}

这是我得到的输出。

3 19 7 3 19 12 3 19 7 3 19 
Process finished with exit code 0

似乎无法理解为什么它会多次读取相同的数据。任何帮助表示赞赏。

Answer 1

您的 add() 方法存在错误。

这里有小错误：

if (item < curr.data) curr.left = add(item, curr.left);
if (item > curr.data) curr.right = add(item, curr.left);

真的应该是：

if (item < curr.data) curr.left = add(item, curr.left);
if (item > curr.data) curr.right = add(item, curr.right);

此外，我还发现了另一个潜在问题。您应该处理您尝试插入的值等于当前节点的值的情况。所以条件应该是：

if(item <= curr.data) curr.left = add(item, curr.left);

否则，您永远不会递归并且永远不会添加新节点。

希望对您有所帮助！

java 中的 BST 实现出现错误

BST implementation in java giving errors

java

binary-search-tree