0

这是 12 年级的作业。其中一个问题要求我们在 BTree 类中编写一个方法，该方法采用 BNode 或整数，并从树中删除该节点。

这是我尝试过的：

public void delete(BNode b){
    if(b==null){
        return;
    }
    if(b.getLeft()==null && b.getRight()==null){

        b = null;
    }
    else{
        //System.out.println("boiboi");
        BNode tmp = b;
        b = null;
        add(tmp.getLeft());
        add(tmp.getRight());
        tmp = null;
    }
}
public void delete(int v){
    //System.out.println("gord");
    delete(find(v));
}

这是我认为正确的添加和查找方法：

public BNode find(int v){
    return find(v, root);
}
public BNode find(int v, BNode branch){
    if(branch == null || branch.getVal() == v){
        return branch;
    }
    if(v<branch.getVal()){
        return find(v, branch.getLeft());
    }
    else{//else if(v>branch.getVal())
        return find(v, branch.getRight());
    }
}
public void add(int v){
    if(root == null){
        root = new BNode(v);
    }
    else{
        add(v, root);
    }
}
public void add(int v, BNode branch){
    if(v == branch.getVal()){
        return;
    }
    if(v<branch.getVal()){
        if(branch.getLeft() == null){
            branch.setLeft(new BNode(v));
        }
        else{
            add(v, branch.getLeft());
        }
    }
    else{
        if(branch.getRight() == null){
            branch.setRight(new BNode(v));
        }
        else{
            add(v, branch.getRight());
        }
    }
}
public void add(BNode n){
    if(n==null){
        return;
    }
    add(n.getVal());
}

这是我的测试课：

    BTree bTree = new BTree();
    bTree.add(50);
    bTree.add(60);
    bTree.add(40);
    bTree.add(35);
    bTree.add(55);
    bTree.add(45);
    bTree.add(51);
    bTree.delete(60);
    bTree.display();

输出仍然是我添加的所有内容：35 40 45 50 51 55 60 即使我尝试删除 51 这是最简单的情况，仍然是相同的输出。任何帮助或建议将不胜感激，谢谢。

4

2 回答 2

2

从 BST 中删除节点时，需要注意三种情况。

  1. 如果它是一片叶子，请继续删除。

  2. 如果一个节点只有 1 个子节点，只需将其子节点连接到其父节点。[您显然需要一些辅助方法来获取ParentOfNode 等]

  3. 如果一个节点有2个孩子，则在右子树中找到最小的元素。并将其值放入当前节点并删除该节点。

更多信息在这里。 http://www.cs.sunysb.edu/~skiena/373/notes/lecture6/lecture6.html

于 2013-03-27T03:50:49.243 回答
0 
/* Algorithm to delete a record from a B-tree of order n.
The field used indicates how many keys in the node are being used. */
    q = NULL;
    p = tree;
    while (p) {
        i = nodesearch(p, key);
        q = p;
        if (i < used(p) -1 && key == k(p,i)) {
            found = TRUE;
            position = i;
            break;
        }
        p = son(p,i);
    }
    if (!found)
    /* error - item not found */
    else if (subtree(p)) {
        /* node is not a leaf */
        if (used(p) > ((n-1)/2)+1)
            /* no underflow */
            delkey (p, position, key);
        else {
            /* Statements to replace key to be deleted */
            /* with successor in father node. */
            replace (p, position, fsucc(p));
            p0 r1 p1 r2 p2 r3 ……. pn-1 rn-1 pn
            q = &fsucc(p);
            qpos = index of fsucc;
            if (used(rbrother(p)) > ((n-1)/2)+1)
                replace (q, qpos, sonsucc(q));
            else
                while (q && used(q) < (n-1)/2) {
                    concatenate(q, brother(q));
                    q = father(q);
                }
        }
    }
    else /* is a leaf */
    delkey(p, position, key);
}
于 2016-08-28T13:09:38.577 回答