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

Моя программа 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();
        }
}

java binary-search-tree
person user985626    schedule 08.10.2011    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Я думаю, вы не справляетесь с

случай 1: где удаляемый узел является конечным узлом

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

часть else if должна быть примерно такой.

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

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

person Keen Sage    schedule 08.10.2011

arrow_upward
1
arrow_downward

Написание разборчивого кода облегчает обнаружение ошибок — как вам, так и другим. Первым шагом является выбор более выразительных имен переменных, чем 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())

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

person meriton    schedule 08.10.2011

arrow_upward
0
arrow_downward

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

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

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

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

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

person Gary    schedule 08.10.2011