C语言二叉搜索树统计单词出现次数的word_count函数问题排查

你的代码存在两处核心逻辑错误，直接导致统计结果异常：

• 二叉树构建逻辑颠倒：word_observe 插入节点时左右子树方向写反。strcmp(s1, s2) 返回值小于0时代表s1字典序小于s2，按照二叉搜索树左子树值 < 当前节点值 < 右子树值的规则，比当前节点小的单词应存入左子树，更大的存入右子树，原代码逻辑完全相反，树结构不符合遍历预期。
• 递归返回值丢失：word_count 递归查找子树时，没有返回子递归的查询结果。原逻辑仅在当前节点刚好匹配目标单词时返回count值，递归进入左右子树查询时，子函数返回的结果被直接丢弃，最终无论是否查到单词都会走到函数末尾返回-1，仅当根节点恰好是目标单词时能返回正确结果。

修复后完整代码 #

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct tnode {
  char *word;
  int count;
  struct tnode *left;
  struct tnode *right;
} tnode;

tnode *word_observe(char *word, tnode *node) {

        if (node != NULL) {
                if (strcmp(node->word, word) == 0) {
                        node->count++;
                        return node;
                } else if (strcmp(node->word, word) < 0) {
                        // 目标单词更大，存入右子树
                        node->right = word_observe(word, node->right);
                } else {
                        // 目标单词更小，存入左子树
                        node->left = word_observe(word, node->left);
                }
        } else {
                tnode *newnode = (tnode*)malloc(sizeof(tnode));
                newnode->word = strdup(word);
                newnode->count = 1;
                newnode->left = NULL;
                newnode->right = NULL;
                node = newnode;
        }
  return node;
}


int word_count(char *word, tnode *node) {
        if (node != NULL) {
                if (strcmp(node->word, word) == 0) {
                        return node->count;
                } else if (strcmp(word, node->word) < 0) {
                        // 目标更小，递归查找左子树并返回结果
                        return word_count(word, node->left);
                } else {
                        // 目标更大，递归查找右子树并返回结果
                        return word_count(word, node->right);
                }
        }
        // 遍历到空节点说明单词不存在，返回-1
        return -1;
}

int main(void) {
  tnode *counts = NULL;

  counts = word_observe("dog", counts);
  counts = word_observe("dog", counts);

  counts = word_observe("apple", counts);
  counts = word_observe("hello", counts);
  counts = word_observe("pineapple", counts);
  counts = word_observe("pineapple", counts);
  counts = word_observe("pineapple", counts);

  counts = word_observe("zebra", counts);
  counts = word_observe("zebra", counts);
  counts = word_observe("zebra", counts);
  counts = word_observe("zebra", counts);

  printf("apple: %d\n", word_count("apple", counts));
  printf("dog: %d\n", word_count("dog", counts));
  printf("pineapple: %d\n", word_count("pineapple", counts));
  printf("zebra: %d\n", word_count("zebra", counts));

  return 0;
}

运行结果 #

修复后代码执行输出如下，符合预期：

apple: 1
dog: 2
pineapple: 3
zebra: 4

注：原代码缺失了stdio.h、stdlib.h、string.h三个必要头文件的引入，修复版本已补充，否则会出现隐式声明编译警告/错误。

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