C语言将存储词频的二叉树转为结构体数组并按规则排序问题

现有代码问题排查 #

• findFreq函数递归调用时没有返回递归结果，会导致查询频率时返回值异常，需要补充return语句
• inOrder遍历函数逻辑错误，遍历完左子树后直接return当前根节点，右子树永远不会被访问，且你循环调用该函数每次都会返回根节点，所以数组内存储的全是根节点数据，不可能得到正确结果
• 固定大小的heads数组上限只有50，当单词总数超过50时会发生数组越界

具体实现步骤 #

步骤1：实现节点填充数组的遍历函数 #

你需要写一个带索引参数的中序遍历函数，遍历二叉树的同时把所有节点指针存入数组：

void fillArray(node* root, node** arr, int* index) {
    if (root == NULL) return;
    fillArray(root->left, arr, index);
    arr[*index] = root;
    (*index)++;
    fillArray(root->right, arr, index);
}

步骤2：实现排序比较函数 #

调用标准库qsort实现自定义排序规则：频率降序，同频率按单词字母升序：

int compare(const void* a, const void* b) {
    node* na = *(node**)a;
    node* nb = *(node**)b;
    if (na->frequency != nb->frequency) {
        // 频率高的排在前面，降序排列
        return nb->frequency - na->frequency;
    } else {
        // 频率相同按字母升序排列
        return strcmp(na->word, nb->word);
    }
}

步骤3：主函数中调用逻辑 #

替换你原来j = countWords(root)之后的错误代码：

int total = countWords(root);
// 动态分配节点指针数组，避免固定大小越界
node** arr = (node**)malloc(total * sizeof(node*));
int index = 0;
fillArray(root, arr, &index);
// 排序
qsort(arr, total, sizeof(node*), compare);
// 输出结果
for(int i = 0; i < total; i++) {
    printf("%s %d\n", arr[i]->word, arr[i]->frequency);
    // 如果要写入文件也可以在这里加fprintf逻辑
}
// 用完释放数组
free(arr);

其他bug修复 #

findFreq函数补充return语句，修正后代码：

int findFreq(node *root, char findWord[MAXSIZE])
{
    if(root!=NULL)
    {
        if(strcmp(findWord, root->word)==0)
        {
            return root->frequency;
        }
        else if(strcmp(findWord, root->word)>0)
        {
            return findFreq(root->right, findWord);
        }
        else if(strcmp(findWord, root->word)<0)
        {
            return findFreq(root->left, findWord);
        }
        else
            return -1;
    }
    else
        return -1;
}

同时建议将void main改为标准的int main()，函数结束前加return 0;符合C语言标准。

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