C实现的前缀表达树

前缀表达树(Trie, Prefix Tree)又称单词查找树是一种多叉树结构， 前缀表达式的主要思路是，根节点开始 根节点不包含字符， 除根节点外每一个子节点都包含一个字符，将从根到某一节点的 字符连接起来形成对应的字符串， 最后在节点中设置一个标记，标记该节点之前的路径是否构成一个单词， 从而实现单词查找。

前缀表达数的实质是，用空间换时间，利用字符串存在的公共前缀来减少字符串比较的次数，从而提高查询效率。 特别是对于字符集较少的应用，前缀表达式能取得较好的效果。 常见的前缀表达式应用包括，字符串检索、词频统计、字符串排序、前缀匹配等。 下面我们用C来实现下前缀表达树。

这里使用的字符串集合为小写英文字母， 在表达式节点中 加一个标记标记表达式分支是否为一个单词， 每一个表达式分支又有相应数目的子节点。

#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();
}

接着我们实现一个函数插入节点， 对于一个新的单词，分析它所有的前缀，是否已经存在于树中，若不存在创建 最后标记单词。

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;
}

查找前缀表达式节点的过程就是从根开始寻找对应的分支， 返回分支节点。

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;
}

若要检查一个单词是否存在，只需要查找其前缀表达式节点和单词标识。

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;
}

以上是前缀表达树最基础的功能， 下面添加一个测试用例，

#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]