C語言實現二叉搜索樹統計單詞頻率：從節點定義到完整程式

專案目標

使用二叉搜索樹（BST）統計文本中單詞出現頻率。每個節點存儲單詞、計數、左右子樹指針。利用 BST 有序特性，實現 O(log n) 平均查找/插入，最終中序遍歷輸出按字典序排列的統計結果。

核心資料結構

#define MAX_WORD_LEN 32

typedef struct BSTNode {
    char word[MAX_WORD_LEN];
    int count;
    struct BSTNode *left;
    struct BSTNode *right;
} BSTNode, *BSTree;

• word：固定長度字元陣列，避免動態分配碎片
• count：該單詞出現次數
• left/right：左右子樹指針，構成遞歸結構

關鍵函數實現

1. 字串比較：cmp_str

// 返回 1 若 s < t，0 若 s >= t（簡化兩值邏輯）
int cmp_str(const char *s, const char *t) {
    for (int i = 0; s[i] == t[i]; i++)
        if (s[i] == '\0') return 0;  // 相等
    return (s[i] - t[i]) < 0 ? 1 : 0;
}

設計為只返回 0/1，避免 strcmp 的三值（-1,0,1）增加邏輯分支。

2. 安全字串複製：str_copy

void str_copy(char *dest, const char *src) {
    while ((*dest++ = *src++) != '\0');
}

解決結構體中字元陣列無法直接賦值（`node->word = val` 非法）的問題。

3. 插入/統計：bst_insert

void bst_insert(BSTree *root, const char *word) {
    if (*root == NULL) {
        *root = (BSTree)malloc(sizeof(BSTNode));
        str_copy((*root)->word, word);
        (*root)->count = 1;
        (*root)->left = (*root)->right = NULL;
        return;
    }
    if (cmp_str(word, (*root)->word)) {
        bst_insert(&(*root)->left, word);   // 更小 → 左子樹
    } else if (cmp_str((*root)->word, word)) {
        bst_insert(&(*root)->right, word);  // 更大 → 右子樹
    } else {
        (*root)->count++;                   // 相等 → 計數++
    }
}

4. 中序遍歷輸出：inorder_print

void inorder_print(BSTree root) {
    if (root) {
        inorder_print(root->left);
        printf("[%-20s] count: [%d]\n", root->word, root->count);
        inorder_print(root->right);
    }
}

中序遍歷 BST 產生遞增序列，此處即字典序輸出。

5. 釋放記憶體：bst_destroy

void bst_destroy(BSTree root) {
    if (root) {
        bst_destroy(root->left);
        bst_destroy(root->right);
        free(root);
    }
}

後序遍歷釋放，避免野指針。

完整主程式

int main() {
    BSTree root = NULL;
    // 硬編碼測試數據（實際可改為文件讀取）
    const char *words[] = {"hello", "hey", "hello", "ok", "hey", "hey", "hey"};
    int n = sizeof(words) / sizeof(words[0]);

    for (int i = 0; i < n; i++) bst_insert(&root, words[i]);

    printf("單詞頻率統計（字典序）:\n");
    inorder_print(root);

    bst_destroy(root);
    return 0;
}

運行結果

單詞頻率統計（字典序）:
[hello               ] count: [2]
[hey                 ] count: [4]
[ok                  ] count: [1]

工程擴展方向

1. 文件輸入：使用 `fscanf(fp, "%31s", buf)` 逐詞讀取，配合 `isalpha` 過濾標點
2. 大小寫無關：插入前統一 `tolower`
3. 平衡樹優化：引入 AVL/紅黑樹，保證最壞 O(log n)
4. 多線程：Map-Reduce 風格分片統計再合併
5. 持久化：遍歷序列化到磁碟，支援斷點續傳

常見坑點總結

| 坑點 | 現象 | 修正 | |------|------|------| | 字串直接賦值 | `node->word = val` 編譯通過但運行崩潰 | 用 `strcpy` 或自定義複製 | | 比較函數三值邏輯 | `if (strcmp < 0) ... else if (strcmp > 0) ...` 易漏等號 | 封裝為兩值 `cmp_str` | | 未檢查 malloc 失敗 | 記憶體耗盡時段錯誤 | 生產代碼必須判空 | | 遞歸深度過大 | 極端不平衡樹導致棧溢位 | 改用迭代或平衡樹 |

總結

本文展示了從資料結構定義、核心操作封裝、記憶體管理到完整業務流程的標準 C 語言 BST 開發範式。掌握此模板，可快速構建符號表、詞頻統計、路由表等鍵值查找系統。