c++ - 从二叉搜索树中删除节点

Question

在下面的代码中，我尝试实现一个基本的删除操作。但是，甚至在开始复杂的删除部分之前，我都未能删除leaf node。我想这可能与定义变量的位置有关，但是我无法解决它。任何想法，将不胜感激。

我想删除节点的部分基本上是作为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

delete操作员不会按照您的想法去做。它的作用是将对象使用的内存标记为未使用，这意味着它可以再次使用（它也调用对象的析构函数，但这与这里无关）。

它不会做的是修改任何指向已删除对象的指针，你必须自己做。

因此，该分支的正确代码必须访问已删除节点的父节点，并将其leftorright字段（取决于已删除节点是哪个）设置为NULL. 只有这样你才能真正delete的节点。