Узел BST без дочерних элементов не удаляется - PullRequest
Новая
       9

Узел BST без дочерних элементов не удаляется

0 голосов
/ 18 ноября 2018

Мой BST не удаляет узел без дочерних элементов после удаления узла с дочерними элементами.

Удалить функцию: 

private Node remove(Node current, Pair k) throws DictionaryException {
        if (current == null) {
            throw new DictionaryException("Key does not exist");
        }

        if (k.compareTo(current.data.getKey()) < 0) {
            current.left = remove(current.left, k);
        } else if (k.compareTo(current.data.getKey()) > 0) {
            current.right = remove(current.right, k);
        } else {
            if (current.left == null && current.right == null) {
                current = null;
            } else if (current.right == null) {
                current = current.left;
            } else if (current.left == null) {
                current = current.right;
            } else {
                Record smallest = smallest(current.right).data;
                current.data = smallest;
                remove(current.right, smallest.getKey());
            }
        }
        return current;
    }

Основной: 

public static void main(String[] args) {
    Pair key1 = new Pair("homework", "text");
    Record record1 = new Record(key1, "hello world");

    Pair key2 = new Pair("course", "text");
    Record record2 = new Record(key2, "world hello");

    Pair key3 = new Pair("class", "text");
    Record record3 = new Record(key3, "bean man");

    Pair key4 = new Pair("computer", "text");
    Record record4 = new Record(key4, "despacito");

    Pair key5 = new Pair("four", "text");
    Record record5 = new Record(key5, "zebras");

    OrderedDictionary od = new OrderedDictionary();

    try {
        od.put(record1);
        od.put(record2);
        od.put(record3);
        od.put(record4);
        od.put(record5);
    } catch (DictionaryException e) {
        System.out.println("exception in main - put");
    }

    try {
        od.remove(key2);
    } catch (DictionaryException e){
        System.out.println("exception in main - remove");
    }

    od.preOrder();

Я ожидаю, что od.preOrder(); вернет "домашнее задание четырехклассного компьютера". Но вместо этого он возвращает: «домашнее задание четыре класса компьютер четыре». По какой-то причине он не удаляет «четверку», которая была правильным потомком «Курса», и я не могу понять, почему.

Ответы [ 2 ]

0 голосов
/ 18 ноября 2018

Разобрался ... просто измените remove(current.right, smallest.getKey()); на current.right = remove(current.right, smallest.getKey()); в remove(Node current, Pair k), чтобы он ссылался на правильный узел

0 голосов
/ 18 ноября 2018

Что-то сложно, когда корневой элемент должен быть удален. Вы можете сделать это, установив root-right-child как right-child самого правого дочернего элемента root-left-child или наоборот, вместо изменения значения корневого элемента и удаления самого правого элемента правой ветви.

...