1

这是要删除的节点有两个孩子的最后一种情况。我无法弄清楚我做错了什么。请帮忙。

    //BTNode has two children
    else if (u.getLeft() != null && u.getRight() != null){
        //if node to delete is root
        BTNode<MyEntry<K,V>> pred = u.getRight();


        while (pred.getLeft().element() != null){
            pred = pred.getLeft();
        }


        BTNode<MyEntry<K,V>> predParent = pred.getParent();
        if (!hasRightChild(pred)){
            predParent.setLeft(new BTNode<MyEntry<K,V>>(null,predParent,null,null));}
        if (hasRightChild(pred)){
            BTNode<MyEntry<K,V>> predChild = pred.getRight();
            predParent.setLeft(predChild);
            predChild.setParent(predParent);
        }


        return returnValue;

好的，像这样修改它？？

        u.setElement(succ.element());



        BTNode<MyEntry<K,V>> succParent = succ.getParent();
        if (!hasLeftChild(succ)){
            succParent.setRight(new BTNode<MyEntry<K,V>>(null,succParent,null,null));}
        if (hasLeftChild(succ)){
            BTNode<MyEntry<K,V>> predChild = succ.getLeft();
            succParent.setRight(predChild);
            predChild.setParent(succParent);
        }


        return returnValue;
4

2 回答 2

1

来自维基百科：

删除有两个子节点的节点：将要删除的节点称为 N。不要删除 N。而是选择它的有序后继节点或它的有序前驱节点 R。将 N 的值替换为 R 的值，然后删除 R。

因此，以左孩子为例，然后在该子树中找到最右边的叶子，然后将要删除的节点的信息替换为叶子的信息，然后轻松删除该叶子。

您可能想要创建一个从子树返回最右边叶子的函数。

于 2012-12-07T00:58:21.387 回答
0

我已经给出了删除 BST 中节点的代码，该代码适用于任何条件，也可以使用 for 循环。

public void delete(int key) {

    Node<E> temp = find(key);
    System.out.println(temp.key);

    for (;;) {
        // case 1 : external node
        if (temp.isExternal()) {
            if (temp.getParent().getrChild() == temp) {
                temp.parent.rightchild = null;
                temp = null;
            } else {

                temp = null;
            }
            break;

        }

        // case2 : one child is null
        else if ((temp.getlChild() == null) || (temp.getrChild() == null)) {
            if ((temp.parent.leftchild != null) && temp.getParent().getlChild().key == temp.key) {
                if (temp.getlChild() == null) {
                    temp.getParent().setLeft(temp.getrChild());
                    temp.getrChild().setParent(temp.getParent());
                    break;

                }

                else
                    temp.getParent().setLeft(temp.getlChild());
                temp.getlChild().setParent(temp.getParent());
            }

            else {
                if (temp.rightchild != null) {
                    System.out.println("in");
                    temp.getParent().setRight(temp.getrChild());

                    temp.getrChild().setParent(temp.getParent());
                    break;

                }

                else
                    temp.getParent().setRight(temp.getlChild());
                temp.getlChild().setParent(temp.getParent());
            }

            break;
        }
        // case 3 : has both the children
        else {
            int t = temp.key;
            temp.key = temp.getlChild().key;
            temp.getlChild().key = t;
            temp = temp.getlChild();

            continue;
        }
    }

}
于 2016-10-30T06:22:18.920 回答