Удаление узла из дерева двоичного поиска

Question

Моя программа Binary Search Tree, похоже, ничего не удаляет, когда я вызываю метод deleteNode. BST построен идеально, он просто удаляет часть узла, которая не работает. Я называю это с моего главного так:

System.out.println("Please enter a number you would like to delete from the tree");
    temp = reader.nextLine();
    try {
        int numTemp = Integer.parseInt(temp);
        TreeNode treeTemp = bst.deleteNode(numTemp, bst.getRoot());
        bst.setRoot(treeTemp);
    }
    catch(Throwable e){
        System.err.println(e);
    }
    bst.printInBST(bst.getRoot());

В моем классе BinarySearchTree я реализую свои методы deleteNode следующим образом:

public TreeNode deleteNode(int x, TreeNode temp){
    if(temp != null){
        if(x > (int)((Integer)temp.getValue())){
            temp.setLeft(deleteNode(new Integer(x), temp.getLeft()));
        }
        else if(x < (int)((Integer)temp.getValue())){
            temp.setRight(deleteNode(new Integer(x), temp.getRight()));
        }
        else if(temp.getLeft() != null & temp.getRight() != null){
            TreeNode temp2 = new TreeNode(temp.getRight().getValue());
            while(temp2.getLeft() != null){
                temp2 = temp2.getLeft();
            }
            temp = temp2;
            temp.setRight(remove(temp.getRight()));
        }
    }
    return temp;
}
public TreeNode remove(TreeNode temp){
        if(temp.getLeft() != null){
            temp.setLeft(remove(temp.getLeft()));
            return temp;
        }
        else {
            return temp.getRight();
        }
}

Answer 1

Я думаю, что вы не обрабатываете

вариант 1: где удаляющий узел является листовым узлом

вариант 2: где у удаляющего узла только 1 дочерний элемент

---

остальное, если часть должна быть что-то вроде этого.

else if( temp.getLeft() != null && temp.getRight() != null ) // Two children
{
      temp.setValue( findMin( temp.getRight() ).getValue());
      temp.setRight ( deleteNode( temp.getValue(), temp.getRight() );
}
else
     temp = ( temp.getLeft() != null ) ? temp.getLeft() : temp.getRight();

return temp;

---

Метод findMin - найти преемника преемника удаляемого узла.

private TreeNode findMin( TreeNode t )
{
        if( t == null )
            return null;
        else if( t.getLeft() == null )
            return t;
        return findMin( t.getLeft() );
}

---

Надеюсь, это ответит на ваш вопрос.

Answer 2

Написание разборчивого кода облегчает обнаружение ошибок - как вами, так и другими.Первым шагом является выбор более выразительных имен переменных, чем temp, temp2 и treeTemp.

Кроме того, на самом деле нет необходимости делать new Integer(x) для назначения параметра метода типа int.Простое написание x вместо этого имеет тот же эффект, быстрее во время выполнения и облегчает определение кода, который имеет значение.

Что касается ошибок, первое, что я вижу:

TreeNode temp2 = new TreeNode(temp.getRight().getValue());

Это создает копию TreeNode.Изменение этой копии не повлияет на исходный узел.Кроме того, копия, вероятно, не имеет установленного left или right, поскольку вы только передаете value в конструктор.Интересно, почему вы думаете, что вам нужна копия?В конце концов, вы тоже не создаете его здесь:

deleteNode(new Integer(x), temp.getRight())

Далее, как указывает Sashwat, если удаляемый узел имеет менее 2 дочерних элементов, ваш код ничего не делает, так как ни один изусловия в deleteNode совпадают.

Answer 3

  public class BSTNode {
  …

  public boolean remove(int value, BSTNode parent) {
        if (value < this.value) {
              if (left != null)
                    return left.remove(value, this);
              else
                    return false;
        } else if (value > this.value) {
              if (right != null)
                    return right.remove(value, this);
              else
                    return false;
        } else {
              if (left != null && right != null) {
                    this.value = right.minValue();
                    right.remove(this.value, this);
              } else if (parent.left == this) {
                    parent.left = (left != null) ? left : right;
              } else if (parent.right == this) {
                    parent.right = (left != null) ? left : right;
              }
              return true;
        }
  }

Answer 4

Не уверен на 100%, если это ваша единственная проблема, но должен:

else if(temp.getLeft() != null & temp.getRight() != null)

на самом деле быть:

else if(temp.getLeft() != null && temp.getRight() != null)

т.е. у вас есть только один & для операции "и", когда у вас должно быть два?