如何使用遞歸刪除二叉查找樹中的節點

Question

我已經嘗試制定刪除函數，用於刪除二叉查找樹內的節點，前提是該節點包含正在搜索的內容。我已經編寫了用於搜索內容的函數的框架，並根據它是否找到內容返回true或false。問題是我似乎無法得到如何爲我的函數實現實際的刪除部分。如果根節點包含我正在查找的值，我不知道如何在刪除後將舊根的子項之一指定爲根位置。我也很難弄清楚如何在刪除節點後刪除子指針，並重新鏈接可能會被切斷的樹的部分，如果我只是斷開包含正在搜索的值的節點。

下面的功能是我到目前爲止有：

bool BSTree::Remove(int content, BSTNode*& bst_node) const { 
// makes sure the tree is not empty (function returns false if it is) 
if (bst_node != NULL) { 
    // checks to see if nodes contents matches content param 
    if (bst_node->GetContents() == content) { 
     // checks to see if the node has children 
     if (bst_node->GetLeftChild() == NULL && bst_node->GetRightChild() == NULL) { 

     } else if (bst_node->GetLeftChild() == NULL) { 

     } else if (bst_node->GetRightChild() == NULL) { 

     } else { 

     } 
     return true; 
    // checks to see if the content of node is less/greater than content param 
    } else if (content < bst_node->GetContents()) { 
     if (bst_node->GetLeftChild() != NULL) 
      return Remove(content, bst_node->GetLeftChild()); 
    } else if (content > bst_node->GetContents()) { 
     if (bst_node->GetRightChild() != NULL) 
      return Remove(content, bst_node->GetRightChild()); 
    } 
    } 
    return false; 
} 

我加入了什麼：

bool BSTree::Remove(int content, BSTNode*& bst_node) { 
    BSTNode* parent = bst_node; 
    if (bst_node == NULL) { 
    return false; 
    } else { 
    if (content == bst_node->GetContents()) { 
     if (bst_node->GetLeftChild() == NULL && bst_node->GetRightChild() == NULL) { 
     if (bst_node == root_) { 
      Clear(); 
     } else { 
      // code for deleting leaf 
      bst_node->SetContents(0); 
      bst_node = NULL; 
      delete bst_node; 
      size_--; 
     } 
     } else if (bst_node->GetLeftChild() == NULL) { 
     // code for deleting node with only right child 
     if (bst_node == root_) { 
      parent = bst_node->GetRightChild(); 
      bst_node->SetContents(0); 
      bst_node = NULL; 
      delete bst_node; 
      root_ = parent; 
     } else { 

     } 
     size_--; 
     } else if (bst_node->GetRightChild() == NULL) { 
     // code for deleting node with only left child 
     if (bst_node == root_) { 
      parent = bst_node->GetLeftChild(); 
      bst_node->SetContents(0); 
      bst_node = NULL; 
      delete bst_node; 
      root_ = parent; 
     } else { 

     } 
     size_--; 
     } else { 
     // code for deleting node with two children 
     size_--; 
     } 
    } else if (content < bst_node->GetContents()) { 
     if (bst_node->GetLeftChild() == NULL) { 
     return false; 
     } else { 
     return Remove(content, bst_node->GetLeftChild()); 
     } 
    } else if (content > bst_node->GetContents()) { 
     if (bst_node->GetRightChild() == NULL) { 
     return false; 
     } else { 
     return Remove(content, bst_node->GetRightChild()); 
     } 
    } 
    } 
    return true; 
} 

助手功能刪除功能：的

int BSTree::FindMin(BSTNode* bst_node) const { 
    if (bst_node != NULL) { 
    if (bst_node->GetLeftChild() != NULL) 
     return FindMin(bst_node->GetLeftChild()); 
    return bst_node->GetContents(); 
    } 
    return 0; 
} 

Answer 1

一個可能的方法刪除一個節點就是用他的直接繼承者替換掉它的葉子，這樣就不會中斷樹的invari螞蟻。

節點的後繼節點是其右子樹的最左邊的子節點，所以一旦到達要刪除的節點，就搜索後繼節點並交換節點。完成後，搜索葉片並將其刪除。當你拿走最左邊的孩子時，你確定葉子會有一個NULL左邊的孩子。它它有一個正確的孩子，用正確的孩子取代葉子，就是這樣。

用於二叉搜索樹的常用實現是讓Remove返回一個節點，因此您可以通過返回節點來重塑樹，而不必爲孫子案例而煩惱。