数据结构——Trie树

Trie树（字典树、前缀树、单词查找树 或 键树）

1.数据结构

结构特点：

1. 根节点（root）不包含字符，除根节点外的每一个子节点都包含一个字符。

2. 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。

3. 每个节点都带一个**标记**，用于判断从根节点开始到该字符是否构成一个完整的单词。即当该字符标记为true，则该字符是某个单词的结尾。

4. 以空间换时间。利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。

2.算法模板与理解

int son[N][26], cnt[N], idx;//son[父亲的位置][儿子的名字]=儿子的位置，26代表每个节点能延申出去26条边（26个字母）
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量，即cnt[]为标记

// 插入一个字符串
void insert(char *str) {
    int p = 0;
    for (int i = 0; str[i]; i ++ ) {
        int u = str[i] - 'a';
        if (!son[p][u]) 	son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str) {
    int p = 0;
    for (int i = 0; str[i]; i ++ ) {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;//如果没有u这个子节点
        p = son[p][u];
    }
    return cnt[p];//返回这个字符串出现的次数
}