在C++中爲二叉搜索樹製作刪除函數

已編輯*：我正在研究二叉搜索樹的刪除功能。我現在正在處理第一個案件。我認爲這是正確的，但我想知道是否可以遞歸或更有效地完成。任何幫助表示讚賞。假設BSTSearch搜索一個節點，如果該節點是一個葉節點，則isLeaf返回true，並且每個節點都有一個允許它們訪問其父節點的指針。在C++中爲二叉搜索樹製作刪除函數

void 
BinarySearchTree::BSTDelete(int x, BSTNode *node){ 

    BSTNode *deleteNode; 
    deleteNode = BSTSearch(x,node); 

    if(isLeaf(deleteNode)){ 

     if(deleteNode->sortkey > (deleteNode->parent)->sortkey){ 
      delete (deleteNode->parent)->right; 
      (deleteNode->parent)->right = NULL; 
     } 

     else{ 
      delete (deleteNode->parent)->left; 
      (deleteNode->parent)->left = NULL; 
     } 
    }

來源

2012-12-18 CoffeeIsProgramming

從樹中刪除可能是一項困難的操作。考慮你需要知道你正在刪除的節點的父節點，所以你可以更新當前指向你感興趣的節點的子指針。然後考慮你將要放置當前節點（可能多於一個）孩子的位置，而不會違反你可能有的任何排序約束（BST肯定有這個約束）。在某些情況下，您可能需要重新平衡一直到樹的根部... – twalberg

「高效」是一個相對術語，並且已經研究了各種二叉搜索樹，每種樹都有自己的優缺點。請參閱AVL，紅黑，Splay，Treap，Tango等樹木... – Cornstalks

這看起來不正確。您正在刪除'deleteNode'，然後訪問它以將其父項中的指針設置爲NULL。您應該將這些行更改爲'deleteNode-> parent-> right = NULL;刪除deleteNode;'。 – Mankarse

您不需要指向父級的指針。這裏是一個應該工作的遞歸版本：（通過引用（&）），如果你不知道，允許你修改變量，類似於通過指針傳遞; BSTNode *&是一個通過引用傳遞的指針，所以我們可以修改節點 - >左/右（指針）的值（不只是它們指向的值））

void BinarySearchTree::BSTDelete(int x, BSTNode *&node) 
{ 
    if (node == NULL) 
     return; 
    if (x == node->sortKey) 
    { 
     if (isLeaf(node)) 
     { 
     delete node; 
     node = NULL; 
     } 
     else 
     { 
     // other stuff goes here 
     } 
     return; 
    } 
    else if (x < node->sortKey) 
     BSTDelete(x, node->left); 
    else 
     BSTDelete(x, node->right); 
}

來源

2012-12-24 06:15:38 Dukeling

在C++中爲二叉搜索樹製作刪除函數

回答

相關問題