C語言實現二叉搜索樹：單詞統計完整案例（創建、查找、中序遍歷）

經典 K&R 風格案例：讀取標準輸入文本，提取單詞，插入二叉搜索樹（BST）統計詞頻，最後中序遍歷輸出按字典序排列的單詞與計數。完美演示結構體自引用、指針操作、動態內存、遞歸樹操作。

數據結構定義

struct tnode {
    char *word;           // 單詞字符串（動態分配）
    int count;            // 出現次數
    struct tnode *left;   // 左子樹（較小單詞）
    struct tnode *right;  // 右子樹（較大單詞）
};

核心函數

1. 獲取單詞

// 從 stdin 讀取下一個單詞（字母開頭的字母數字序列）
int getword(char *word, int lim) {
    int c, getch(void);
    void ungetch(int);
    char *w = word;
    while (isspace(c = getch())) ; // 跳過空白
    if (c != EOF) *w++ = c;
    if (!isalpha(c)) { *w = '\0'; return c; } // 非字母開頭直接返回
    for (; --lim > 0; w++)
        if (!isalnum(*w = getch())) { ungetch(*w); break; }
    *w = '\0';
    return word[0];
}

2. 節點分配與字符串複製

struct tnode *talloc(void) {
    return (struct tnode*)malloc(sizeof(struct tnode));
}
char *strdup_custom(char *s) { // 避免與庫函數衝突
    char *p = malloc(strlen(s) + 1);
    if (p) strcpy(p, s);
    return p;
}

3. 插入/查找（遞歸）

struct tnode *addtree(struct tnode *p, char *w) {
    int cond;
    if (p == NULL) { // 新單詞
        p = talloc();
        p->word = strdup_custom(w);
        p->count = 1;
        p->left = p->right = NULL;
    } else if ((cond = strcmp(w, p->word)) == 0) {
        p->count++; // 已存在，計數++
    } else if (cond < 0) {
        p->left = addtree(p->left, w); // 遞歸左子樹
    } else {
        p->right = addtree(p->right, w); // 遞歸右子樹
    }
    return p;
}

4. 中序遍歷輸出

void treeprint(struct tnode *p) {
    if (p) {
        treeprint(p->left);
        printf("%4d %s\n", p->count, p->word);
        treeprint(p->right);
    }
}

主程序

int main() {
    struct tnode *root = NULL;
    char word[100];
    while (getword(word, 100) != EOF)
        if (isalpha(word[0]))
            root = addtree(root, word);
    treeprint(root);
    return 0;
}

運行示例

$ ./word_freq < article.txt
   1 a
   2 and
   1 article
   3 binary
   5 search
   2 tree
   ...

關鍵技術點總結

擴展方向

• 平衡樹（AVL/紅黑）保證 O(log N) 最壞情況。
• Trie 樹優化前綴查找。
• 內存池分配節點減少 malloc 開銷。
• 釋放樹內存：後序遍歷 free(p->word); free(p);。