Почему не удаляется мое бинарное дерево поиска? - PullRequest
Новая
       14

Почему не удаляется мое бинарное дерево поиска?

0 голосов
/ 28 апреля 2018

Двоичное дерево поиска может потребовать большой программы, поэтому я решил не публиковать остальную часть кода. Я получаю некоторые исключения нулевого указателя, потому что я думаю, что я не понимаю, где поставить фигурную скобку в моей функции удаления. Может кто-нибудь помочь мне найти проблему и объяснить, почему? Ввод / вывод внизу: 

// other functions above
public void delete(int key) {
    LinkNode x = firstNode;
    LinkNode temp = search(x, key);
    if(temp == null) {
        System.out.println("delete " + key + " - not found.");
        return;
    }
    LinkNode y = delete(temp); // line 252
    System.out.println("deleted " + y.key + ".");
}   

private LinkNode delete(LinkNode x) {
    LinkNode t = firstNode;
    if(x.left == null || x.right == null) {
        t = x;
    } else {
        t = successor(x);
    }
    if(t.left != null) {
        x = t.left;
    } else {
        x = t.right;
    }
    if(x != null) {
        x.parent = t.parent;
    }
    if(t.parent == null) {
        firstNode = x;
    } else if(t == t.parent.left) {
        t.parent.left = x;
    } else {
        t.parent.right = x;
    }
    if(t != x) {
        t.parent = x.parent; // line 280
    }
    return t;
}

Вот некоторые входные и выходные данные. Похоже, другие мои функции работают правильно. 

insert 3
inserted 3.
insert 5
inserted 5.
insert 2
inserted 2.
insert 20
inserted 20.
insert 100
inserted 100.
insert 42
inserted 42.
inorder
inorder traversal:
2 3 5 20 42 100
min
min is 2.
max
max is 100.
delete 3
deleted 5.
delete 42
Exception in thread "main" java.lang.NullPointerException
        at Bst.delete(Bst.java:280)
        at Bst.delete(Bst.java:252)
        at prog.main(prog.java:52)

Не стесняйтесь спрашивать о любых других моих функциях. Спасибо за любую помощь

1 Ответ

0 голосов
/ 01 мая 2018

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

else {
    x = t.right;
}

Возможно, это должно выглядеть как приведенный выше код и быть: 

else if (t.right != null) {
    x = t.right;
}
...