二叉搜索树相加算法的实现

Question

我必须在 java 中为 BST 实现一个添加方法，但我的添加功能无法正常工作。有人可以帮我吗？

private boolean add(E x, BinaryNode<E> currentNode){

        if (currentNode == null){
            currentNode = new BinaryNode<>(x);
            size++;
            return true;
        }

        if (currentNode.element.compareTo(x) == 0){
            return false;
        }

        else if((currentNode.element.compareTo(x) < 0)){

            if(currentNode.left == null){
                currentNode.left = new BinaryNode<>(x);
                size++;
                return true;

            } else {
                add(x, currentNode.left);
            }

        }

        else if(currentNode.element.compareTo(x) > 0){

            if(currentNode.right == null){
                currentNode.right = new BinaryNode<>(x);
                size++;
                return true;

            } else {
                add(x, currentNode.right);
            }

        }

        return false;
    }

    public boolean add(E x){
        return this.add(x, root);
    }

Answer 1

我看到的一个问题是，当您分配根元素时，您将其分配给局部变量。这显然是行不通的。

private boolean add(E x, BinaryNode<E> currentNode){
  /////// REMOVE
        if (currentNode == null){
            currentNode = new BinaryNode<>(x);
            size++;
            return true;
        }
  ///////

并添加这个

public boolean add(E x){
    if( root == null ) {
      root = new BinaryNode<>(x);
      size++;
      return true;
    }  else
      return this.add(x, root);
}

Answer 2

基本上，子树的根可能会改变，这是一个递归，为了让它工作，return值应该是子树的新根，不管它是否改变。

以下是从我的 BST 实现中提取的 add() 方法 Java，所有测试用例都通过了：

/**
 * Add a new value.
 *
 * @param v
 */
@Override
public void add(T v) {
    root = add(root, v);
}

/**
 * Add to a subtree start from given node.
 *
 * @param current root of a subtree to add node to,
 * @param v
 * @return the new root of subtree,
 */
protected BSTNode<T> add(BSTNode<T> current, T v) {
    if (current == null) { // subtree is empty,
        size++;
        return new BSTNode<>(v);
    }

    // compare,
    int compareFlag = v.compareTo(current.value);

    // check this or subtree,
    if (compareFlag < 0) { // smaller, go to left subtree,
        current.left = add(current.left, v);
    } else if (compareFlag > 0) { // larger, go to right subtree,
        current.right = add(current.right, v);
    } else { // equals, ignore it,
    }

    return current;
}

二叉搜索树相加算法的实现

Implementation of binary search tree add algorithm

java

algorithm

binary-tree

binary-search-tree

data-structures