Связанное бинарное дерево и удаление листа - PullRequest
Новая
       9

Связанное бинарное дерево и удаление листа

0 голосов
/ 12 января 2020

В данный момент я делаю проект и, похоже, не могу пройти мимо Logi c.

Какой лучший способ удалить лист? В данный момент я попадаю в исключение NullPointerException и не знаю почему. Любая помощь будет принята с благодарностью. 

@Override
    public E removeLeaf(Position<E> p){
        BinaryTreeNode<E> node = ((BinaryTreeNode<E>) p);
        E element = node.element();
        if(node.left != null && node.right != null) throw new InvalidPositionException();
        node.parent.left = null;
        node.parent.right = null;
        return element;
    }

Код Ниже приведен мой класс тестирования 

public class BinaryTreeTester {

    public static void main(String[] args) {

        LinkedBinaryTree<Integer> numTree = new LinkedBinaryTree<>();
        Position<Integer> nroot = numTree.addRoot(1);
        System.out.println(numTree.toString());
        Position<Integer> nchild1 = numTree.insertChild(nroot, 6);
        System.out.println(numTree.toString());
        Position<Integer> nchild2 = numTree.insertChild(nroot, 7);
        Position<Integer> nchild11 = numTree.insertChild(nchild1, 8);
        Position<Integer> nchild12 = numTree.insertChild(nchild1, 23);
        Position<Integer> nchild20 = numTree.insertChild(nchild12, 11);
        Position<Integer> nchild21 = numTree.insertChild(nchild12, 21);
        System.out.println(numTree.toString());

        numTree.removeLeaf(nchild20);

        System.out.println(numTree.toString());
    }
}

1 Ответ

0 голосов
/ 12 января 2020

Я вижу две проблемы в следующем фрагменте кода: 

if(node.left != null && node.right != null) throw new InvalidPositionException();
node.parent.left = null;
node.parent.right = null;

Первая строка, кажется, проверяет, является ли узел действительно leaf , но логика c неправильно. В настоящее время он проверяет, имеет ли узел два дочерних элемента, но он даже должен отклонить ситуацию, когда у него есть один дочерний элемент. Таким образом, && должен быть ||.

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

if (node.left != null || node.right != null) throw new InvalidPositionException();
if (node.parent.left == node) {
    node.parent.left = null;
} else {
    node.parent.right = null;
}

Это все еще не очень хорошо подходит для граничного случая, когда узел является root сам (последний узел в дереве). В этом случае parent, вероятно, будет null (это зависит от вашей реализации). Так что вам нужно добавить условие для этого. И если у вас есть ссылка root на узел root дерева, то этот root должен быть очищен: 

if (node.left != null || node.right != null) throw new InvalidPositionException();
if (node.parent == null) {
    root = null; // this assumes you have such a variable...
} else if (node.parent.left == node) {
    node.parent.left = null;
} else {
    node.parent.right = null;
}
...