在使用二叉搜索树删除功能时遇到问题

Question

我正在尝试从二叉搜索树中删除给定值。函数 returns 如果给定值存在则为 1，否则为 0。我认为我没有正确返回值。正确的值似乎被删除了，但我在不应该的时候打印了一条删除消息，表明该函数在不应该的时候返回 0。谁能帮我发现我的错误？谢谢

/*Remove data from BST pointed to by rootRef, changing root if necessary.
* For simplicity's sake, always choose node's in-order
* successor in the two-child case.
* Memory for removed node should be freed.
* Return 1 if data was present, 0 if not found. */

int removeBST(struct TreeNode** rootRef, int data)
{  
  struct TreeNode* heir;
  struct TreeNode* prev;

  if(*rootRef == NULL)
  {
    return 0;
  }

  if(data < (*rootRef)->data)
  {
    removeBST(&(*rootRef)->left, data);
  }
  else if(data > (*rootRef)->data)
  {
    removeBST(&(*rootRef)->right, data);
  }
  else
  {
    struct TreeNode* temp;

    if((*rootRef)->right == NULL)
    {
      temp = *rootRef;
      *rootRef = (*rootRef)->left;
      free(temp);
    }
    else if((*rootRef)->left == NULL)
    {
      temp = *rootRef;
      *rootRef = (*rootRef)->right; 
      free(temp);
    }
    else
    {
      heir = (*rootRef)->left;
      prev = *rootRef;

      while(heir->right != NULL)
      {
        prev = heir;
        heir = heir->right;
      } 

      (*rootRef)->data = heir->data;

      if(prev != *rootRef)
      {
        prev->right = heir->left;
      }
      else
      {
         prev->left = heir->left;
      }
      free(heir);
   }
   return 1;
  }
  return 0;
}

Answer 1

替换

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

和

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

当您调用该函数时，您没有使用 return 值。

Answer 2

当它递归调用自身时，它需要return递归调用的值。所以改变：

removeBST(&(*rootRef)->left, data);

至：

return removeBST(&(*rootRef)->left, data);

右边的情况也类似。没有这个，它只是落空并且 returning 0 对于这些情况。

在使用二叉搜索树删除功能时遇到问题

Having trouble with a binary search tree remove function

c

binary-search-tree