C語言實現二叉樹建立與查找：單詞統計實戰

前言

二叉搜尋樹（BST）是經典資料結構，適用於動態集合的插入、查找與有序遍歷。本文透過一個完整的單詞統計程式，示範如何用 C 語言實現二叉樹的節點配置、插入邏遞遞歸、中序遍歷輸出。

資料結構定義

#define MAXWORD 100

struct tree_node {
    char *word;           // 指向單詞字串
    int count;            // 出現次數
    struct tree_node *left;  // 左子樹
    struct tree_node *right; // 右子樹
};

注意：原始碼中 int *count 應為 int count，此處已修正。

核心函數實現

1. 節點配置與字串複製

struct tree_node *tree_alloc(void) {
    return (struct tree_node *) malloc(sizeof(struct tree_node));
}

char *strdup(char *s) {
    char *p = (char *) malloc(strlen(s) + 1); // +1 存放 '\0'
    if (p != NULL) strcpy(p, s);
    return p;
}

2. 插入/更新節點

struct tree_node *addtree(struct tree_node *p, char *w) {
    int cond;
    if (p == NULL) {                 // 新單詞，建立節點
        p = tree_alloc();
        p->word = strdup(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;
}

3. 中序遍歷輸出

void treeprint(struct tree_node *p) {
    if (p != NULL) {
        treeprint(p->left);
        printf("%8d %s\n", p->count, p->word);
        treeprint(p->right);
    }
}

主程式流程

int main() {
    struct tree_node *root = NULL;
    char word[MAXWORD];

    while (getword(word, MAXWORD) != EOF) {
        if (isalpha(word[0]))       // 只統計以字母開頭的單詞
            root = addtree(root, word);
    }
    treeprint(root);
    return 0;
}

getword 函數（未列出）負責從標準輸入讀取下一個單詞，略過非字母數字字元。

執行範例

$ ./word_freq < article.txt
       12 the
        8 and
        5 tree
        3 binary
        1 structure

常見問題與優化

• 記憶體洩漏：程式結束前未釋放樹節點與字串，生產環境需實現 free_tree 遞歸釋放。
• 極端情況退化：若輸入單詞已排序，樹退化為鏈表，查找變 O(n)。可引入 AVL 或紅黑樹平衡機制。
• 大小寫敏感：strcmp 區分大小寫，若需忽略可改用 strcasecmp 或統一轉小寫。

這個範例完整展示了二叉樹在實際文字處理中的應用，是掌握指標操作、遞歸思維與動態記憶體管理的優秀練習。