удаление узла из двоичного дерева поиска в Java - PullRequest
Новая
       10

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

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

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

вот мой код: 

public boolean delete(E e) {
    BSTDelete<E> d = new BSTDelete<E>();
    boolean deleted = d.delete(e, root);
    if (deleted)
        size -= 1;
    return deleted;
}

public class BSTDelete<E extends Comparable<E>> {

    public boolean delete(E e, TreeNode<E> root) {
        if (root == null) {
            return false;
        }
        if (e == root.element) {
            if (root.right == null && root.left == null) {
                root = null;
            } else if (root.right == null) {
                root = root.left;
            } else if (root.left == null) {
                root = root.right;
            } else

                root.element = minValue(root.left);
            delete(root.element, root.left);
            // Delete the inorder successor

        } else if (e.compareTo(root.element) < 0) {
            delete(e, root.left);
        } else {
            delete(e, root.right);
        }
        return true;
    }

    E minValue(TreeNode<E> root) {
        E minv = root.element;
        while (root.right != null) {
            minv = root.right.element;
            root = root.right;
        }
        return minv;
    }

}

вот тест, который продолжает терпеть неудачу.Второй assertEquals говорит, что i.next () это «Беатрис», а не «Карл» 

    BST <String>b = new BST<String>();
    b.insert("Arthur");
    b.insert("Beatrice");
    b.insert("Carl");
    b.insert("Dagmar");

    b.delete("Beatrice");
    Iterator <String> i = b.iterator();

    assertEquals(i.next(), "Arthur");
    assertEquals(i.next(), "Carl");
    assertEquals(i.next(), "Dagmar");

    }

, а вот мой класс BSTInorderIterator: 

 public class BSTInorderIterator<E extends Comparable<E>> implements 
 java.util.Iterator<E> {
 int current = 0;
 ArrayList<E>  list  = new ArrayList<E>();
 private TreeNode<E> root;


 public BSTInorderIterator(TreeNode<E> root) {
    list = new ArrayList<E>();
    inorder(root);
    }


/** Inorder traversal from the root */
public void inorder() {
    inorder(root);
}

/** Inorder traversal from a subtree */
public void inorder(TreeNode<E> root) {
    if (root.left != null)
        inorder(root.left);
    list.add(root.element);
    if (root.right != null)
        inorder(root.right);
}

@Override
/** More elements for traversing? */
public boolean hasNext() {


    return current < list.size();
}

@Override
/** Get the current element and move to the next */
public E next() {


    return list.get(current++);
}

@Override
/** Remove the current element */
public void remove() {
    // to do: make this work correctly
}

1 Ответ

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

Метод delete внутри класса BSTDelete является рекурсивным методом, однако вы никогда не возвращаете рекурсивные вызовы метода.Следовательно, ваш метод delete будет возвращать false только когда вы вызываете его как d.delete(e, root), где root равно null.

Например, даже если delete(e, root.left) может вернуть false, поскольку root.left равно null, ваш исходный вызов метода вернет true, поскольку вы не вернете результат delete(e, root.left).

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

public boolean delete(E e, TreeNode<E> root) {
    if (root == null) {
        return false;
    }
    if (e == root.element) {
        if (root.right == null && root.left == null) {
            root = null;
        } else if (root.right == null) {
            root = root.left;
        } else if (root.left == null) {
            root = root.right;
        } else

        root.element = minValue(root.left);
        return delete(root.element, root.left);
        // Delete the inorder successor

    } else if (e.compareTo(root.element) < 0) {
        return delete(e, root.left);
    } else {
        return delete(e, root.right);
    }
    return true;
}
...