我的二进制搜索树实现中的 insert() 方法有什么问题？

Question

我试图创建一个递归方法来将一个元素插入到我的二叉搜索树中；但是，我似乎无法在我的代码中找到错误（我怀疑它与引用有关）。

public class BST<E extends Comparable<E>> {

    private class BSTNode implements Comparable<BSTNode> {

        public E data;
        public BSTNode left;
        public BSTNode right;

        public BSTNode(E data) {
            this.data = data;
        }

        @Override
        public int compareTo(BSTNode o) {
            return this.data.compareTo(o.data);
        }
    }

    public BSTNode root;

    public void insert(E data) {
        insertRec(root, new BSTNode(data));
    }

    private void insertRec(BSTNode current, BSTNode newNode) {
        if (current == null) {
            current = newNode;
            return;
        }
        if (current.compareTo(newNode) > 0) {
            insertRec(current.right, newNode);
        }
        else if (current.compareTo(newNode) < 0) {
            insertRec(current.left, newNode);
        }
    }

Answer 1

这毫无意义：

 if (current == null) {
            current = newNode;
            return;
        }

current.right 和 current.right 可以是 null，因此您永远不会真正向节点添加内容。

要设置您需要做的事情，即 current.right = newNode

这应该有效：

public class BST<E extends Comparable<E>> {

    private class BSTNode implements Comparable<BSTNode> {

        public E data;
        public BSTNode left;
        public BSTNode right;

        public BSTNode(E data) {
            this.data = data;
        }

        @Override
        public int compareTo(BSTNode o) {
            return this.data.compareTo(o.data);
        }
    }

    public BSTNode root;

    public void insert(E data) {
        root = insertRec(root, new BSTNode(data));
    }

    private BSTNode insertRec(BSTNode current, BSTNode newNode) {
        if (current == null){
            return newNode;
        }

        if (current.compareTo(newNode) > 0) {
           current.right = insertRec(current.right, newNode);
        } else {
            current.left = insertRec(current.left, newNode);
        }

        return current;
    }
}

我的二进制搜索树实现中的 insert() 方法有什么问题？

What's wrong with my insert() method in my Binary Search Tree implementation?

java

data-structures

binary-search-tree