前綴表達(dá)樹(Trie, Prefix Tree)又稱單詞查找樹是一種多叉樹結(jié)構(gòu)， 前綴表達(dá)式的主要思路是，根節(jié)點(diǎn)開始 根節(jié)點(diǎn)不包含字符， 除根節(jié)點(diǎn)外每一個子節(jié)點(diǎn)都包含一個字符，將從根到某一節(jié)點(diǎn)的 字符連接起來形成對應(yīng)的字符串， 最后在節(jié)點(diǎn)中設(shè)置一個標(biāo)記，標(biāo)記該節(jié)點(diǎn)之前的路徑是否構(gòu)成一個單詞， 從而實(shí)現(xiàn)單詞查找。

前綴表達(dá)數(shù)的實(shí)質(zhì)是，用空間換時間，利用字符串存在的公共前綴來減少字符串比較的次數(shù)，從而提高查詢效率。 特別是對于字符集較少的應(yīng)用，前綴表達(dá)式能取得較好的效果。 常見的前綴表達(dá)式應(yīng)用包括，字符串檢索、詞頻統(tǒng)計(jì)、字符串排序、前綴匹配等。 下面我們用C來實(shí)現(xiàn)下前綴表達(dá)樹。

這里使用的字符串集合為小寫英文字母， 在表達(dá)式節(jié)點(diǎn)中 加一個標(biāo)記標(biāo)記表達(dá)式分支是否為一個單詞， 每一個表達(dá)式分支又有相應(yīng)數(shù)目的子節(jié)點(diǎn)。

#define KEY_SET_NUM 26

typedef struct trie_node {
    bool is_word;
    struct trie_node *children[KEY_SET_NUM];
} trie_node;

typedef struct trie {
    trie_node *root;
} trie;

static trie_node *new_trie_node() {
    trie_node *n = malloc(sizeof(trie_node));
    if (!n)
        err_exit(MEM_FAIL);
    
    n->is_word = false;
    memset(n->children, 0, sizeof(trie_node *)*KEY_SET_NUM);

    return n;
}

void init_trie(trie *t) {
    t->root = new_trie_node();
}

接著我們實(shí)現(xiàn)一個函數(shù)插入節(jié)點(diǎn)， 對于一個新的單詞，分析它所有的前綴，是否已經(jīng)存在于樹中，若不存在創(chuàng)建 最后標(biāo)記單詞。

void insert_trie(trie *t, const char *word) {
    trie_node *cur = t->root;
    if (!cur)
        return;

    int word_len = strlen(word);
    for (int i = 0; i < word_len; i++) {
        int ix = word[i] - 'a';
        if (!cur->children[ix])
            cur->children[ix] = new_trie_node();

        cur = cur->children[ix];
    }
    cur->is_word = true;
}

查找前綴表達(dá)式節(jié)點(diǎn)的過程就是從根開始尋找對應(yīng)的分支， 返回分支節(jié)點(diǎn)。

static trie_node * find(trie *t, const char *prefix) {
    trie_node *cur = t->root;

    int word_len = strlen(prefix);
    for (int i = 0; i < word_len; i++) {
        cur = cur->children[prefix[i] - 'a'];
        if (!cur)
            break;
    }
    return cur;
}

若要檢查一個單詞是否存在，只需要查找其前綴表達(dá)式節(jié)點(diǎn)和單詞標(biāo)識。

bool search_trie(trie *t, const char *word) {
    trie_node *cur = find(t, word);
    return cur && cur->is_word;
}

bool start_with_trie(trie *t, const char *prefix) {
    return find(t, prefix) != NULL;
}

以上是前綴表達(dá)樹最基礎(chǔ)的功能， 下面添加一個測試用例，

#define INIT_TRIE(t) trie t; init_trie(&t)
#define FREE_TRIE(t) reset_trie(&t);

void test_tire() {
    const char *word = "banan";
    INIT_TRIE(t);
    insert_trie(&t, word);
    printf("has prefix %d", start_with_trie(&t, "ban"));
    FREE_TRIE(t);
}

代碼清單：
[https://github.com/KevinACoder/Learning/blob/master/ds/trie.h]
[https://github.com/KevinACoder/Learning/blob/master/ds/trie.c]