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

Question

这是我试图解决这个特定问题的地方： http://mycodeschool.com/work-outs/binary-search-trees/7

如果要删除的节点同时具有children，则采用的策略是用其左子树中的最大值替换该节点（我们称之为MAX_LEFT）。然后你可以简单地删除节点MAX_LEFT。我们针对此问题的视频中也讨论了此策略。

我正在尝试通过以下代码解决这个问题。但是有一些问题，我没有得到预期的输出。

struct Node
  {
     int data;
     struct Node* left;
     struct Node* right;
  }

Node* FindMax(Node* root)
{
    if(root==NULL)
    return NULL;

    while(root->right != NULL)
    {
        root = root->right;
    }
    return root;
}
Node* DeleteNodeInBST(Node* root,int data)
{
    if(root==NULL) return root;
    else if(data<=root->data) 
        root->left = DeleteNodeInBST(root->left, data);
    else if (data> root->data)
        root->right = DeleteNodeInBST(root->right, data);
    else
    {
        //No child
        if(root->right == NULL && root->left == NULL)
        {
            delete root;
            root = NULL;   
        }
        //One child 
        else if(root->right == NULL)
        {
            Node* temp = root;
            root= root->left;
            delete temp;
        }
        else if(root->left == NULL)
        {
            Node* temp = root;
            root= root->right;
            delete temp;
        }
        //two child
        else
        {
            Node* temp = FindMax(root->left);
            root->data = temp->data;
            root->left = DeleteNodeInBST(root->left, temp->data);
        }
    }
    return root;
}

Answer 1

在下面的代码段中，在2个else if语句之后，final else语句永远不会执行，因为没有其他可能:

 else if(data<=root->data) 
        root->left = DeleteNodeInBST(root->left, data);
 else if (data> root->data)
        root->right = DeleteNodeInBST(root->right, data);
 else
        ....

Answer 2

这部分

if(data<=root->data)
    root->left = DeleteNodeInBST(root->left, data);
else
    ...

当 data 等于当前节点 root 时，

也会下移到左子树。因此，您将 永远不会 到达第三个 else。尝试将 <= 替换为 <.

Answer 3

知道了。我必须删除 "else if(data<=root->data)" 中的“=”，然后才能正常工作。

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

C++ Delete a node from binary search tree

c++

binary-search-tree