從二叉搜索樹中刪除一個節點

Question

在下面的代碼中，我試圖實現一個基本的刪除操作。但是，即使在複雜的移除部分開始之前，我也無法刪除葉節點。我想這可能與變量的定義有關，但我無法解決它。任何想法，將不勝感激。

我想要刪除節點的部分基本上實現爲delete temp;部分（順便說一句，如果我將它插入爲delete[]temp;它仍然不起作用）。

void remove(int value){ 
     if(root==NULL) 
      cout<<"The list is empty!"<<endl; 
     else { 
      Node *temp=root; 
      while(temp!=NULL) 
      { 
       cout<<"Processing: "<<temp->data<<endl; 
       if(value==temp->data) 
       { 
        cout<<"Data verified"<<endl; 
        //DELETE ROOT 
        if(temp->left && temp->right) //If it has two children 
        { 
         cout<<"Root with two children"<<endl; 
         return; 
        } 
        if(temp->left || temp->right) 
        { 
         cout<<"Root with a single child"<<endl; 
         return; 
        } 
        else { 
         cout<<"Leaf node"<<endl; 
         delete temp; 
         return; 
        } 
       } 
       else if(value<temp->data){ 
        if(temp->left) 
         temp=temp->left; 
        else 
         return; 
       } 
       else{ 
        if(temp->right) 
         temp=temp->right; 
        else 
         return; 
       } 


      } 
     } 
    } 

Answer 1

The delete operator不會做你認爲的事。它所做的是將對象使用的內存標記爲未使用的內存，這意味着它可以再次使用（它也調用對象的析構函數，但在此不重要）。

它是什麼不會做的是修改任何指向已刪除對象的指針，你必須自己做。

因此，該分支的正確代碼將不得不訪問已刪除節點的父代，並將其left或right字段（取決於刪除的節點）設置爲NULL。只有這樣你纔可以實際節點delete。