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

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。只有这样您才能真正删除节点。