C语言二叉树insert()方法调用时循环异常终止问题排查

你的插入函数一共有4类核心逻辑错误，直接导致了你遇到的所有异常现象：

• strcmp返回值判断完全不符合C标准规范

C标准中strcmp(s1, s2)的返回值仅约定三类结果：

1. 两字符串相等时返回0
2. s1大于s2时返回任意正整数
3. s1小于s2时返回任意负整数
   从来没有约定返回值固定为1或-1，多数libc实现会直接返回两个逐位比对字符的ASCII差值，结果可能是任意正负整数。
   你硬编码判断返回值是否等于1、-1，会导致绝大多数比较场景分支错乱：比如两字符串比较结果为2、-2这类非±1值时，既不会走左子树分支也不会走右子树分支，直接落入“编码已存在”的错误分支；部分场景下会跳过父节点赋值逻辑，后续访问未初始化的野指针直接触发段错误，这就是字符串长度不一致时程序直接停止运行的核心诱因。

• 节点插入时机完全错误，直接破坏原有树结构
  你把新节点挂载的逻辑写在了while (ptr != NULL)遍历循环内部，每次指针向下移动一层就立刻把新节点挂到当前父节点上，会直接覆盖父节点原本存储的左/右孩子指针，该节点下的整段原有子树会直接丢失、无法访问。这就是你只能插入首尾元素的根本原因：只有插入根节点、整棵树最左/最右叶子节点时不会覆盖中间子树结构，其余位置插入都会直接破坏树结构。

• 多处野指针未处理

  • 局部变量father声明后未初始化，属于野指针，一旦分支判断异常访问该指针会直接触发内存错误。
  • 传入insert的新节点aux的left、right指针没有被置为NULL，挂载到树上后两个指针指向随机内存地址，后续遍历、删除树的时候会访问非法地址，这就是批量从文件加载节点时主循环直接终止的核心原因。

• 标准库调用参数缺失触发未定义行为
  打印重复编码的语句printf("\n The code %s already exists");中，占位符%s没有传入对应的字符串参数，属于C语言未定义行为，会随机读取栈上内存作为地址，大概率触发程序崩溃。

void insert(tree* aux){
    // 新节点左右指针必须先置空，杜绝野指针
    aux->left = NULL;
    aux->right = NULL;

    // 空树直接作为根节点
    if(root == NULL){
        root = aux;
        return;
    }

    tree *ptr = root;
    tree *father = NULL;
    int duplicate_flag = 0;

    // 遍历阶段只移动指针找插入位置，不做节点挂载
    while(ptr != NULL){
        father = ptr;
        int cmp_result = strcmp(aux->code, ptr->code);
        if(cmp_result > 0){
            // 新编码更大，走右子树
            ptr = ptr->right;
        }else if(cmp_result < 0){
            // 新编码更小，走左子树
            ptr = ptr->left;
        }else{
            duplicate_flag = 1;
            // 补全printf缺失的参数
            printf("\n The code %s already exists", aux->code);
            break;
        }
    }

    // 遍历完成确认无重复后，再把新节点挂到对应位置
    if(duplicate_flag == 0){
        int cmp_result = strcmp(aux->code, father->code);
        if(cmp_result > 0){
            father->right = aux;
        }else{
            father->left = aux;
        }
    }
}

• 你定义的code字段长度为5，需要确认所有摩尔斯编码的长度不超过4个字符，否则会因为没有空间存储字符串结束符\0触发缓冲区溢出，同样会导致程序崩溃。
• 从文件加载节点时，每次malloc申请内存后要先判断返回值是否为NULL，确认内存分配成功后再给字段赋值、调用insert，避免操作空指针。

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