浅谈 Trie 树
什么是 Trie 树？
Trie 树，又称字典树，可用于存储单词。
Trie 树的根节点不表示任何字母，但是除了根节点的所有字母都表示一个字母。
任何一个单词，都可以用一条从根节点出发的路径表示。在路径的终点做一个“结束”标记，对应一个单词的结尾。
举个例子：要存储 work,word,world,hello 这些单词。
红色节点表示“结束”标记。
可以看到，叶子节点都是一个单词的结尾；但是并不是所有的单词结尾都是叶子节点。
再举个例子：假如要多存储一个 worker 单词。
Trie 树的好处之一，如果两个单词有公共前缀，则有公共路径，可以节省空间。
存储结构
Trie 树中的每个节点都可以用一个结构体来存储。
code
struct node{
bool flg; // 结束标记
int son[MAXC]; // 儿子们的“指针”，MAXC表示字符集的大小
}Trie[MAXN]; // MAXN表示Trie树的节点数
节点的字母（值）怎么表示？
一般在程序中，都是去枚举节点 \(i\)，所以一般不用结构体来表示节点的字母。
构建 Trie 树
先分配足够大的空间（Trie 树），也就是定义足够大的 node 数组。
然后每读入一个单词，就插入在 Trie 树当中。
code
#define MAXC 26
struct node{
bool flg;
int son[MAXC];
}Trie[MAXN];
int root=1,tot=1;
void ins(int r,char *s){
int len=strlen(s),val;
for(int i=0;i<len;i++){
val=s[i]-'a';
if(Trie[r].son[val]==0)
Trie[r].son[val]=++tot;
r=Trie[r].son[val];
}
Trie[r].flg=1;
}
查询节点
bool query(int rt,char *s){
int len=strlen(s),val;
for(int i=0;i<len;i++){
val=s[i]-'a';
rt=Trie[rt].son[val];
if(rt==0) return 0;
}
return Trie[rt].flg;
}
此代码可以返回“查询串”（char *s）的结尾的信息。
这里返回了 Trie[rt].flg，仅作示范。在实践中，可以返回 Trie[rt].cnt 等等定义的变量。
例 1 ：单词查找树
算法分析
就是裸的 Trie 树，模板题。
code（这里直接复制了 Alex_Wei 的代码）
#include<bits/stdc++.h>
using namespace std;
string s;
int cnt,q[1<<15][26];//cnt为节点个数，q为儿子编号
int main(){
while(cin>>s){
int pos=0;
for(int i=0;i<s.size();i++){
int ch=s[i]-'A';
if(!q[pos][ch])q[pos][ch]=++cnt;//如果没有这个节点，就新建一个
pos=q[pos][ch];
}
}
cout<<cnt+1<<endl;//本题中root也算一个节点，别忘了+1
return 0;
}