删除二进制搜索树中的节点-C

Question

我目前正在做一个学校项目，我必须为二叉搜索树编写一些辅助函数。其中一个函数从树中删除了一个节点。我正在尝试运行一些测试用例，但似乎无法让它们正常工作。我知道这个问题与我如何使用指针有关，但我不太确定我哪里出错了。

这是代码：

int removeBST (struct TreeNode **rootRef, int data)
{
    struct TreeNode *current = *rootRef;
    struct TreeNode *temp = current;

    if (current == NULL)
        return 0;

    if (data < current->data) 
    {
        current->left = removeBST (&current->left, data);
    }

    if (data > current->data) 
    {
        current->right = removeBST (&current->right, data);
    }

    if (current->left == NULL || current->right == NULL)
        return 0;
    else 
    {
        if (current->left == NULL) {
            temp = current->right;
            current = temp;
            free (temp);
            return 1;
        } 
        else if (current->right == NULL) {
            temp = current->left;
            current = temp;
            free (temp);
            return 1;
        }
        temp = leftRoot (current->right);
        current->data = temp->data;
        current->right = removeBST (&current->right, temp->data);

    }

    return 1;
}

注意：我没有包括leftRoot（）函数，但它相当简单，我知道它做了它应该做的事情（返回子树中最左边的根）下面是我的教授给我们的测试remove函数的代码部分：

  for(i = -4; i < 25; i+=4)
  {
    n = removeBST(&bst, i);
    if(!n) printf("remove did not find %d\n", i);
  }

如果有必要，下面是创建树并插入数据的整个测试代码：

struct TreeNode* bst = NULL;
for(i = 0; i < 23; ++i)
  {
    n = (i*17+11) % 23;
    bst = insertBST(bst, n);
  }

  printf("filled BST: ");
  printTree(bst);
  printf("BST leaves: ");
  printLeaves(bst);
  printf("BST depth = %d\n", maxDepth(bst));
  printf("BST minimum value = %d\n", minValueBST(bst));
  printf("BST isBST = %d\n", isBST(bst));

  for(i = -4; i < 25; i+=4)
  {
    n = removeBST(&bst, i);
    if(!n) printf("remove did not find %d\n", i);  
  }

整个输出是：

filled BST: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 
BST leaves: 0 6 12 17 
BST depth = 8
BST minimum value = 0
BST isBST = 1
remove did not find -4
remove did not find 0
remove did not find 4
(this part repeats all the way up to 24)
BST after removes: 11

由于除了“11”之外的所有内容都不再附加到树，我相当确定我的程序中的某些内容正在分配不应该分配的指针，并且树节点只是在空白中丢失了。有什么想法吗？

编辑：我忘记提供一条信息，被删除节点最左边的子节点应该替换被删除的节点。

Answer 1

我不确定我是否发现了您代码中的所有问题，但这里有一个主要问题：

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

您的函数返回一个int，并由许多返回1或返回0语句证实...

然而你却做到了：

    if (data < current->data) 
    {
        current->left = removeBST (&current->left, data);
    }

    if (data > current->data) 
    {
        current->right = removeBST (&current->right, data);
    }

既然你通过了

这意味着您正在将地址分配给左节点和右节点？这对我来说似乎很奇怪，可能会给你带来问题。

注意：这不是一个解决方案，但它太大，无法放入注释中。

既然你选择了递归，让我看看我是否能帮你解决这个问题...

int removeBST (struct TreeNode **rootRef, int data)
{
    struct TreeNode *current = *rootRef;
    struct TreeNode *temp = current;

    if (current == NULL)
        return 0;

    if (data < current->data) 
    {
        // We don't want to modify things here, just let the next 
        // call take care of it and return what it returns.
        return removeBST(&current->left, data);
    }
    else if (data > current->data) 
    {
        // Same here.
        return removeBST(&current->right, data);
    }
    else 
    {
        if (current->left == NULL) {
            temp = current->right;
            // The rest of the stuff from here moved below.
            // Because I added the else, the return isn't needed 
            // here anymore either, since the one at the bottom 
            // will return 1 anyway.
        } 
        else if (current->right == NULL) {
            temp = current->left;
            // I did the same here.
        }
        else {
            temp = leftRoot (current->right);
            // This was on the outside but really it should be an else 
            // since it means less code...
            // Additionally, once you got the left root why did you decide
            // to remove it too? As far as I can see you only want to 
            // remove this one... If not, then you might have some work 
            // to do here...
        }

        *rootRef = temp; // current and rootRef are not the same. 
                         // You need to use rootRef here so that we 
                         // move the temp pointer to the current one 
                         // (replace it). Think carefully about where 
                         // the pointers are! Pointers also have addresses 
                         // and it matters what address you write to 
                         // where, use pen and paper and draw where things 
                         // point! 
        free (current);  // this means that we can't delete temp! so 
                         // since, we've just deleted the "current" 
                         // pointer we should discard it too...
    }

    return 1;
}

为指针绘制图表。我发现这样或这样的图表对我帮助最大。这并不令人尴尬，它会帮助你理解你在写什么。将这些东西形象化是很重要的，尤其是在你刚刚学习的时候。

我试着把代码修改一下。我承认我没有花尽可能多的时间进行校对，但应该可以给你一个解决方案的想法。不要只是复制/粘贴这个，我不能保证它会起作用。但这应该会帮助你走上正确的道路。