从二叉搜索树中删除一个节点

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。