c++ - 如何从二叉搜索树 C++ 中正确删除节点

Question

我一直试图从我的树中删除特定的值，但不是删除它们，而是将它们设置为 0。与网络上的其他二叉搜索树相比，我的实现似乎非常标准。除了我的 RemoveNode 之外，我所有的其他功能都可以正常工作。

struct Node{
    int key;
    Node *right;
    Node *left;
    Node(int data){
        key=data;
        right=NULL;
        left=NULL;
    }
};
class BST{
private:
    Node *root;

    void AddLeafPrivate(int key,Node *&Ptr){
        if(Ptr==NULL){
            Ptr=createLeaf(key);
        }else if(key<Ptr->key){
            if(Ptr->left!=NULL){
                AddLeafPrivate(key,Ptr->left);
            }else
            {
                Ptr->left=createLeaf(key);
            }
        }
        else if(key>Ptr->key){
            if(Ptr->right!=NULL){
                AddLeafPrivate(key,Ptr->right);
            }else
            {
                Ptr->right=createLeaf(key);
            }
        }
    }
    void PrintInOrderPrivate(Node *Ptr){
    if(Ptr!=NULL){
        if(Ptr->left!=NULL){
            PrintInOrderPrivate(Ptr->left);
        }cout<<Ptr->key<<" ";
        if(Ptr->right!=NULL){
            PrintInOrderPrivate(Ptr->right);
        }

    }else{
        cout<<"tree is empty"<<endl;
    }
    }

    Node *findMin(Node *Ptr){
        if(Ptr->left!=NULL){
            findMin(Ptr->left);
        }else{
            return Ptr;
        }

    }

    void RemoveNodePrivate(int key,Node *parent){
        if(parent==NULL){
            cout<<"EMPTY TREE"<<endl;
            return;
    }else if(key<parent->key){
        RemoveNodePrivate(key,parent->left);
    }else if(key>parent->key){
        RemoveNodePrivate(key,parent->right);
    }else{
        if(parent->left==NULL&&parent->right==NULL){
            delete parent;
            parent=NULL;
        }else if(parent->left!=NULL&&parent->right==NULL){
            Node *temp=parent;
            parent=parent->left;
            delete temp;
            temp=NULL;

        }else if(parent->left==NULL&&parent->right!=NULL){
            Node *temp=parent;
            parent=parent->right;
            delete temp;
            temp=NULL;

        }else if(parent->left!=NULL&&parent->right!=NULL){
            Node *temp=findMin(root->right);
            root->key=temp->key;
            RemoveNodePrivate(temp->key,root->right);

        }
    }


    }

public:
    BST(){
        root=NULL;
    }


    Node *createLeaf(int key){
        Node *n=new Node(key);
        return n;
    }
    void AddLeaf(int key){
        AddLeafPrivate(key,root);
    }

    void PrintInOrder(){
        PrintInOrderPrivate(root);
    }

    void RemoveNode(int key){
        RemoveNodePrivate(key,root);
    }
};

int main()
{
BST tree;
tree.AddLeaf(5);
tree.AddLeaf(8);
tree.AddLeaf(12);
tree.AddLeaf(4);
tree.AddLeaf(3);
tree.AddLeaf(2);
tree.AddLeaf(7);
tree.RemoveNode(5);
tree.PrintInOrder();
cout<<endl;

}

我希望输出为 2 3 4 7 8 12 但相反，它是 2 3 4 7 0 8 12

标签： c++binary-search-tree