为什么我的二叉树删除会删除树的整个左侧部分？

Question

我有一个作业，其中我需要在 C 中实现二叉搜索树。在我尝试为树实现删除函数时，我未能实现不删除整个（或几乎整个）的实现) 树，如果要删除的节点位于左侧。这是我写的函数：

btree_node *btree_remove(const int x, btree_node *root) {
  //if the value cant be found return null;
   if (root == NULL) return root;
  //search for the node to be deleted
   if (x < root->data) {
    root->left = btree_remove(x, root->left);
   }
   
   if (x > root->data){
    root->right = btree_remove(x, root->right);
   }
   else {
    //case when there is no child
     if ((root->left == NULL) && (root->right == NULL)) {
      free(root);
       return NULL;
     }
     //case when it has one child
     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;
      }
     }
      
      //case when it has two children
      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

Answer 1

您需要有一个

if

-

else if

-

else

结构。目前，如果

x < root->data

为 true（事实上，5 < 17), then the first

if

将评估为

true

，

root->left

将被分配给 5（在执行和评估内部

btree_remove

之后），然后

x > root->data

将被false（因为 5 > 5 不为 true）并且

else

将被错误执行。

您真正需要的是区分

x < root->data

与

x > root->data

与

else

，并且像条件一样，这些块也应该是互斥的：

   if (x < root->data) {
    root->left = btree_remove(x, root->left);
   }
   
   else if (x > root->data){
    root->right = btree_remove(x, root->right);
   }
   else {
    //case when there is no child
     if ((root->left == NULL) && (root->right == NULL)) {
      free(root);
       return NULL;
     }
     //case when it has one child
     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;
      }
     }