需要幫助刪除二叉查找樹節點

這是一個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，最簡單的情況下，仍然是相同的產出。任何幫助或建議，將不勝感激，謝謝。

來源

2013-03-27 cook cook

B節點b是[參考]（http://way2java.com/oops-concepts/reference-variables-anonymous-objects/）。 b = null不會修改節點的VALUE，只需將空引用賦給b。你有修改家長的左/右參考。如果它是根目錄，則修改根引用。 – iamsleepy 2013-03-27 03:52:23

謝謝，我想我明白你在說什麼。 – 2013-03-27 03:58:52

從BST中刪除節點時需要注意三種情況。

如果它是一片葉子，就直接刪除。
如果一個節點只有一個孩子，只需將其孩子連接到其父母。 [你顯然需要一些輔助的方法來 getParentOfNode等]
如果一個節點有2個孩子，找到最小的元素在 subtree.And把它的值在當前節點的權利，並刪除該節點。

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

來源

2013-03-27 03:50:49 smk

/* 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-28 13:09:38 jaxkewl

需要幫助刪除二叉查找樹節點

回答

相關問題