为 BST 实现 Add 方法

Question

我正在尝试在 BST 中实现插入方法，但遇到了一些问题。给定周边代码：

public class BinarySearchTree<E> {
  private BinaryNode<E> root;  
  private int size;          
  private Comparator<E> comparator;

    /**
     * Constructs an empty binary search tree, sorted according to the specified comparator.
     */
    public BinarySearchTree(Comparator<E> comparator) {
        root = null;
        size = 0;
        this.comparator = comparator;
    }

    private static class BinaryNode<E> {
        private E element;
        private BinaryNode<E> left;
        private BinaryNode<E> right;

        private BinaryNode(E element) {
            this.element = element;
            left = right = null;
        }   
    }

     //Other methods
}

我的实现有什么问题：


    /**
     * Inserts the specified element in the tree if no duplicate exists.
     * @param x element to be inserted
     * @return true if the the element was inserted
     */
    public boolean add(E x) {
        return add(root, x);
    }

    private boolean add(BinaryNode<E> n, E x) {
        if(n == null) {
            n = new BinaryNode<E> (x);
            size++;
            return true;
        }
        int compResult = comparator.compare(x, n.element);
        
        if(compResult<0){
            return add(n.left, x);
        } else if(compResult>0) {
            return add(n.right, x);
        }else {
            return false;
        }
    }

当测试只插入一个元素时，我得到 null 作为根的 return 值，但我真的看不出出了什么问题。感谢您的帮助！

Answer 1

当你赋值时

    n = new BinaryNode<E> (x)

在 add() 中，您正在分配给局部变量。这不会将新节点添加到树中；没有从现有树到新节点的引用。

有很多方法可以修复它，但这可能是您从未看到 root 从 null 改变的原因；你永远不会在任何地方分配给它。

指针在这里会很好，它们使通过引用传递变量变得更容易，但在 Java 中，我认为您需要以其他方式传递需要放置新节点的位置.我已经 20 年没用过这门语言了，所以我不太确定。

为 BST 实现 Add 方法

Implementing Add Method for BST

java

algorithm

recursion

data-structures

binary-search-tree