我有一个任务,需要用C语言实现一个二叉搜索树.在try 实现树的删除函数时,如果要删除的 node 在左侧,我未能实现不删除整个(或几乎整个)树的实现.这是我写的函数:

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;
      }
   }
 }

我使用INSERT函数创建的二叉树如下所示:

   10
  /  \
 5    17
/ \
2  NULL

然后,当我try 删除 node (5)时,预期的结果是:

      10
     /  \
    2    17
   / \
NULL  NULL

使用此函数的结果是:

      17
     /  \
    2    NULL
   / \
NULL  NULL

推荐答案

你需要有一个if-else if-else的 struct .目前,如果x < root->data为真(实际上,5<;17),则前if将求值为true,root->left将被赋值为5(在执行和求值内部btree_remove之后),然后x > root->data将为假(因为5>;5不为真),并且else将被错误地执行.

您实际需要的是区分x < root->datax > root->dataelse,并且,就像条件一样,块也应该是互斥的:

   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;
      }
     }

C++相关问答推荐

Zig将std.os.argv转换为C类型argv

C语言中字符数组声明中的标准

MISRA C:2012 11.3违规强制转换(FLOAT*)到(uint32_t*)

双指针指向常量双指针的指针类型赋值不兼容

致命:ThreadSaniizer:在Linux内核6.6+上运行时意外的内存映射

如何在CANbus RX/TX FIFO起始地址寄存器(ATSAME 51)的特定地址初始化数组?

在WSL关闭/重新启动后,是什么原因导致共享对象依赖关系发生更改?

什么是.c.h文件?

是否需要包括<;errno.h>;才能使用perror?

GCC奇怪的行为,有fork 和印花,有换行符和不换行符

合并对 struct 数组进行排序

用于计算位数和的递归C函数

在下面的C程序中,.Ap0是如何解释的?

当我在34mb的.mp4文件中使用FREAD时,我得到了一个分段错误,我如何解决它?

在文件描述符上设置FD_CLOEXEC与将其传递给POSIX_SPOWN_FILE_ACTIONS_ADCLOSE有区别吗?

存储和访问指向 struct 的指针数组

程序打印一些随机空行

无法理解 fgets 输出

为什么程序在打印每个数字之前要等待所有输入?

inline 关键字导致 Clion 中的链接器错误