C语言二叉搜索树插入后root始终为NULL无法建树问题求助

核心错误（root始终为NULL的直接原因） #

你的insert函数本身会返回新的根节点指针，但你在main中调用insert(root, string);时没有接收返回值。C语言函数参数是值传递，函数内部修改形参root不会影响外部的实参root，所以原来的root永远为NULL。
修复方法：将调用语句改为root = insert(root, string);

其他致命逻辑错误 #

• 插入右子树的递归调用写错：strcmp>0的分支里你仍然调用了insert(root->left, newWord);，需要改为insert(root->right, newWord);，否则所有节点都会向左插入，完全不符合二叉搜索树规则
• 递归插入子节点未接收返回值：直接写insert(root->left, newWord);无法修改父节点的子节点指针，需要改为root->left = insert(root->left, newWord);，右子树同理
• depth计算逻辑错误：每插入一个节点就给当前根的depth+1的逻辑完全错误，节点depth应为父节点depth+1，只需在创建新节点时赋值即可，无需修改父节点depth
• main函数中inOrder(root);位置错误：你将它放在switch的default分支之后，永远不会被执行，应该放到for循环外侧，所有操作执行完成后再调用
• inOrder函数声明返回int但实际无return语句，直接改为void返回值即可

修正后的核心代码片段 #

修正后的insert函数 #

node* insert(node* root, char newWord[MAXSIZE], int parent_depth)
{
    if(root == NULL)
    {
        node* temp = (node*) malloc(sizeof(node));
        temp->frequency = 1;
        temp->depth = parent_depth + 1;
        temp->left = NULL;
        temp->right = NULL;
        strcpy(temp->word, newWord);
        printf("新节点创建：%s，深度%d\n", newWord, temp->depth);
        return temp;
    }
    int cmp_res = strcmp(newWord, root->word);
    if(cmp_res < 0)
    {
        printf("往%s左子树插入%s\n", root->word, newWord);
        root->left = insert(root->left, newWord, root->depth);
    }
    else if(cmp_res > 0)
    {
        printf("往%s右子树插入%s\n", root->word, newWord);
        root->right = insert(root->right, newWord, root->depth);
    }
    else
    {
        printf("单词%s重复，频率+1\n", newWord);
        root->frequency +=1;
    }
    return root;
}

修正后的main中insert调用 #

case 1:
    printf("insert %s\n", string);
    root = insert(root, string, 0); // 根节点父深度设为0，最终根节点depth为1
    break;

修正后的inOrder函数 #

void inOrder(node* root)
{
    if(root != NULL)
    {
        inOrder(root->left);
        printf("单词：%s\t频率：%d\t深度：%d\n", root->word, root->frequency, root->depth);
        inOrder(root->right);
    }
}

额外功能实现提示 #

如果要按频率从高到低输出所有单词，可以先遍历整棵树把所有节点存入数组，再用qsort自定义排序规则按频率降序排列后输出即可。

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