为何二叉树删除操作会移除整个左子树？C语言BST实现问题

我在完成C语言实现二叉搜索树（BST）的作业时，删除函数出现异常：删除左子树中的节点时，会删掉整个（或几乎整个）左子树。

问题代码 #

btree_node *btree_remove(const int x, btree_node *root) {
  // 未找到节点则返回空
   if (root == NULL) return root;
  // 查找待删除节点
   if (x < root->data) {
    root->left = btree_remove(x, root->left);
   }
   
   if (x > root->data){
    root->right = btree_remove(x, root->right);
   }
   else {
    // 无子女节点情况
     if ((root->left == NULL) && (root->right == NULL)) {
      free(root);
       return NULL;
     }
     // 仅有一个子女的情况
     else {
        if (root->right == NULL){
            btree_node* temp = root->left;
            free(root);
            return temp;
        }
        if (root->left == NULL) {
            btree_node* temp = root->right;
            free(root);
            return temp;
        }
     }
      
      // 有两个子女的情况
      if((root->left != NULL) && (root->right !=NULL)){
        btree_node* minNode = findMin(root->right);
        root->data = minNode->data;
        root->right = btree_remove(minNode->data, root->right);
        return root;
      }
   }
 }

测试场景 #

构建的二叉树：

10
  /  \
 5    17
/ \
2  NULL

删除节点5的预期结果：

10
     /  \
    2    17
   / \
NULL  NULL

实际执行结果：

17
     /  \
    2    NULL
   / \
NULL  NULL

问题原因 #

1. 分支逻辑错误：使用两个独立的if判断x < root->data和x > root->data，而非if-else if结构。这会导致递归过程中可能同时触发多个分支，破坏树的指针关联。
2. 返回值缺失：函数在非删除节点的执行路径中没有明确返回值，触发未定义行为，导致指针被随机值覆盖。

修复方案 #

将分支判断改为if-else if结构，并确保所有路径都有明确返回值：

btree_node *btree_remove(const int x, btree_node *root) {
    if (root == NULL) return root;

    // 用else if确保同一时间只走一个搜索分支
    if (x < root->data) {
        root->left = btree_remove(x, root->left);
    } else if (x > root->data) {
        root->right = btree_remove(x, root->right);
    } else {
        // 无子女节点
        if (root->left == NULL && root->right == NULL) {
            free(root);
            return NULL;
        }
        // 仅左子女
        else if (root->right == NULL) {
            btree_node* temp = root->left;
            free(root);
            return temp;
        }
        // 仅右子女
        else if (root->left == NULL) {
            btree_node* temp = root->right;
            free(root);
            return temp;
        }
        // 有两个子女，取右子树最小节点替换当前节点值
        btree_node* minNode = findMin(root->right);
        root->data = minNode->data;
        root->right = btree_remove(minNode->data, root->right);
    }
    // 所有非删除节点路径，返回原节点指针
    return root;
}

修复说明 #

• if-else if结构避免了递归时同时处理左右子树的错误，确保搜索路径唯一。
• 函数末尾的return root保证所有执行路径都有明确返回值，消除未定义行为。
• 调整单一子节点的判断为else if，简化逻辑，避免冗余判断。

内容的提问来源于stack exchange，提问作者johanwww