c - 从二进制搜索树中删除根指针指向的数据

我很难弄清楚如何使用双指针从BST中删除数据，然后根据需要更改根目录。这是我正在尝试的方法，但是当我对其进行测试时，它删除了不应删除的数字...关于存在缺陷的任何想法？

编辑：下面是答案后的新代码...

    int removeBST(struct TreeNode** rootRef, int data)
    {

      while (*rootRef && (*rootRef)->data != data)
      {

         if ((*rootRef)->data > data)
         {

             rootRef = &(*rootRef)->left;
         }
         else if ((*rootRef)->data < data)
         {
              rootRef = &(*rootRef)->right;
         }
     }

    if (*rootRef)
    {
        struct TreeNode *tmp = *rootRef;
        if (rootRef->left == NULL && rootRef->right == NULL) // no children
        {
        free(tmp);
        }
        else if (rootRef->left->left == NULL && rootRef->right->right == NULL) // one child
{
  rootRef = rootRef->left;
}
else
{
  rootRef = inOrderSuccessor(rootRef);
  removeBST(**rootRef, data);
}

        return 1;
    }

    return 0;

}

最佳答案

我认为问题出在*rootRef = tmp->left;行。

此行尝试删除节点rootRef。它实际上所做的只是将节点替换为其左子节点，如果rootRef仅具有左子节点，这是正确的。但是，如果有合适的孩子，它将成为孤儿。

您需要做的是正确处理删除操作，如下所示：


如果rootRef没有子代，即rootRef->left == NULL && rootRef->right == NULL，
只需删除该节点。
如果rootRef只有一个孩子，请用该孩子替换rootRef。
如果rootRef有两个子代，请用其in-order后继者替换rootRef的值，然后递归删除该节点，直到达到情况1或2。


An example on removing a node from a BST。

您的代码必须类似于以下内容：

int removeBST(struct TreeNode** rootRef, int data) {
    while (*rootRef && (*rootRef)->data != data) {
        ...
    }


    struct TreeNode* prootRef = *rootRef;
    if (prootRef) {
        if(prootRef->left && prootRef->right) // Both children exist
            // Find its in-order successor
            ...
        }
        else if(prootRef->left) { // Only left child exists
           // Replace rootRef by its left child
           ...
        }
        else if(prootRef->right) { // Only right child exists
           // Replace rootRef by its right child
           ...
        }
        else { // rootRef is a leaf node
           // Delete rootRef
           ...
        }

        return 1;
    }

    return 0;
}