二叉搜索樹遞歸刪除

當我試圖找到我的刪除功能的最大值時，我的程序不斷破壞。我想要做的是用最大的左樹覆蓋用戶想要刪除的內容，然後刪除該節點。一旦到達第一個Else，它就會一直斷裂。遞歸正在打破我的想法。我的缺點在哪裏？二叉搜索樹遞歸刪除

這是帶有其私有遞歸兄弟的remove函數。

template<typename TYPE> 
bool BinarySearchTree<TYPE>::remove(TYPE& data) 
{ 
    bool found = search(dataOut); 
    if(found) 
     TRoot = Premove(TRoot, data); 
    return found; 
} 

template<typename TYPE> 
Node<TYPE>* BinarySearchTree<TYPE>::Premove(Node<TYPE>* root, TYPE& data) 
{ 
    Node<TYPE>* del; 
    Node<TYPE>* max; 
    if(root) 
    { 
     if(root->data > data) 
      root->left = Premove(root->left, data); 
     else if(root->data < data) 
      root->right = Premove(root->right, data); 
     else 
     { 
      if(root->left && root->right) 
      { 
       max = root->left; 
       while(max->data < max->right->data) 
        max = max->right; 
       root->data = max->data; 
       max = Premove(root, max->data); 

      } 
      else 
      { 
       del = root; 
       root = (root->right) ? root->right : root->left; 
       delete pDel; 
      } 
     } 
    } 
    return root; 
}

來源

2013-04-14 Derp

你能描述一下「破」的含義嗎？（關於代碼，而不是你的想法） –

好吧，它似乎很好地通過了一段時間，但當我試圖刪除'max'它只是進入一個無限循環。 – Derp

問題是最有可能在這裏： while(max->data < max->right->data) max = max->right;

您正在運行從樹上（max->right將成爲最終NULL）。其實，因爲它是二叉搜索樹，所以不需要比較data。只要在可能的情況下向右走即可：while (max->right) max=max->right;

另請注意此分支中的最後一項分配：還有兩個問題。首先，而不是max = Premove(...)你應該做root->left = Premove(...)（否則你不會修改根 - >左引用）。其次，您應該撥打Premove獲得root->left而不是root：root->left = Premove(root->left, max->data);（否則您只能獲得無限遞歸）。

來源

2013-04-14 20:20:19 Inspired

我覺得你的while語句應該是這樣的：

while(max && max->right && max->data < max->right->data)

在某些情況下，在你的代碼，max或max->right可能是NULL，並導致RUN_TIME錯誤。

來源

2013-04-14 20:22:31

二叉搜索樹遞歸刪除

回答

相關問題