Реализация алгоритма добавления бинарного дерева поиска - PullRequest
Новая
       54

Реализация алгоритма добавления бинарного дерева поиска

0 голосов
/ 24 февраля 2019

Я должен реализовать метод добавления для BST в Java, но не могу заставить мою функцию добавления работать.Может ли кто-нибудь мне помочь? 

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

Ответы [ 2 ]

0 голосов
/ 24 февраля 2019

Как правило, корень поддерева может измениться, и это рекурсия, чтобы заставить его работать, возвращаемое значение должно быть новым корнем поддерева, несмотря на то, изменилось оно или нет.

Ниже приведены дополнения() метод, взятый из моего BST, подразумеваемого в 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;
}
0 голосов
/ 24 февраля 2019

Одна проблема, которую я вижу, состоит в том, что когда вы назначаете корневой элемент, вы назначаете его локальной переменной.Это, очевидно, не работает. 

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