Я пытаюсь реализовать метод удаления в моей программе Binary Search Tree - PullRequest
Новая
       20

Я пытаюсь реализовать метод удаления в моей программе Binary Search Tree

0 голосов
/ 26 апреля 2019

Я пытаюсь реализовать метод удаления для бинарного дерева поиска.Программа в основном завершена, за исключением метода удаления.Я чувствовал, что мой метод удаления завершен и логически имеет смысл для меня без каких-либо ошибок, пока я не выполню тест JUnit.Мои узлы содержат строки в качестве данных.

Когда я проверяю приведенный ниже код, он возвращает true, когда удаляет первый добавленный узел, который кажется правильным, но затем, когда я пытаюсь удалить его снова, он все равно возвращает true, как если бы узел все еще оставался верным.там, хотя мой метод должен был установить его на ноль.Мой код и метод JUnit ниже.Никакие другие методы в коде не дают никаких проблем.Может кто-нибудь определить, что должно быть исправлено в моем методе? 

public boolean remove(String s) {
        return remove(root , s);
    }


    public boolean remove(Node root, String s) {
        Node parent = root;
        if(root == null) {
            return false;
        }
        if(root.data == s) {
            if(root.left == null && root.right == null && getHeight(root) == 1) {//if only node
                root = null;
                parent = null;
                return true;
            }
            if(root.left == null && root.right == null && getHeight(root) > 1) { //if leaf(no children)
                if(parent.right == root) {
                    parent.right = null;
                    return true;
                }
                if(parent.left == root) {
                    parent.left = null;
                    return true;
                }
            }
            if(root.left != null && root.right != null && getHeight(root) > 1) { //if node with two children
                Node temp = root;
                while(temp.right != null) { //find biggest node in left subtree and replace root with that
                    temp = root.right;
                }
                root = temp;
                return true;
            }
            if(root.left == null && root.right != null) { //if node with right child only
                parent.left = root.right;
                return true;
            }
            if(root.left != null && root.right == null) { //if node with left child only
                parent.left = root.left;
                return true;
            }
        }
        if(root.data != s){
            if(root.data.compareTo(s) < 0) {
                parent = root;
                remove(root.left, s);
            }
            if(root.data.compareTo(s) > 0) {
                parent = root;
                remove(root.right, s);
            }
        }
        return false;
    }

Тест JUNIT, где он не проходит: 

BinarySearchTree bst = new BinarySearchTree();

        assertFalse(bst.remove("abc"));


        bst.add("abc");
        assertFalse(bst.remove("cba"));
        assertTrue(bst.remove("abc"));

        assertFalse(bst.remove("abc"));

приведенный выше код работает до последнего вызова удаления.

...