一。trie树是什么东西呢？
他用一个很有意思的别名叫字典树，字典树毫无疑问就是相当于一个字典，字典是干什么的？
有人会说：当然是用来查单词的的了！
对，trie树说百就是用来查单词的。
大家看这样一个题：
求一个数出现的频率？
大家肯定会想到，求频率呀，用于个简单的hash或者一个堆就搞定了。
但问题来了，如果内存有限呢？还能这么玩吗？所以这里我们就可以用trie树来压缩下空间，因为公共前缀都是用一个节点保存的。
二。说这些太没趣了，下面我没来看一个有趣的图
从上面的图中，我们或多或少的可以发现一些好玩的特性。
第一：根节点不包含字符，每条边对应一个字母。
第二：从根节点到某一节点，路径上经过的字符连接起来，就是该节点对应的字符串。
第三：每个节点对应一项前缀。叶节点对应最长前缀，即单词本身。
第四：单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支，root->i->in。同理，ate, age, adv, 和ant共享前缀"a"，所以他们共享从根节点到节点"a"的边。
查询操纵非常简单。比如要查找int，顺着路径i -> in -> int就找到了。
三。大家肯定想知道trie树的广泛用途吧
第一：词频统计。
可能有人要说了，词频统计简单啊，一个hash或者一个堆就可以打完收工，但问题来了，如果内存有限呢？还能这么
玩吗？所以这里我们就可以用trie树来压缩下空间，因为公共前缀都是用一个节点保存的。
第二: 前缀匹配
就拿上面的图来说吧，如果我想获取所有以"a"开头的字符串，从图中可以很明显的看到是：and,as,at，如果不用trie树，
你该怎么做呢？很显然朴素的做法时间复杂度为O(N2) ，那么用Trie树就不一样了，它可以做到h，h为你检索单词的长度，
可以说这是秒杀的效果。
举个例子：现有一个编号为1的字符串”and“，我们要插入到trie树中，采用动态规划的思想，将编号”1“计入到每个途径的节点中，
那么以后我们要找”a“，”an“，”and"为前缀的字符串的编号将会轻而易举
四。代码实现
插入一个单词
void insert()//插入单词s{ len=strlen(s);//单词s的长度 root=0;//根节点编号为0 for(int i=0;i 查询一个单词
bool find(){ len=strlen(s); root=0;//从根结点开始找 for(int i=0;s[i];i++) { int x=s[i]-'a';// if(trie[root][x]==0) return false;//以root为头结点的x字母不存在，返回0 root=trie[root][x];//为查询下个字母做准备，往下走 } return true;//找到了} 五。例题
最经,skyzhong得到了一本好厉害的字典，这个字典里整整有n个单词(1<=n<=200000)
现在skyzhong需要在字典里查询以某一段字母开头的单词
如:skyzhong想查询a
那么只要是a开头的单词就可以了
skyzhong只想知道里面有没有这一个单词（因为没有他就不查了）
若有，请输出YES。若没有，请输出NO
第一行一个数n
第二行到第n+1行，一行一个字符串
再下一行一个数m，表示skyzhong想要查询的次数
接着m行，一行一个字符串，表示skyzhong想要查的东西
3
asd
asfdghj
asfd
3
asd
asdghj
asf
字符串只有小写字母，且长度≤8
（该题可被认为是求一个数是否出现过的类型）
/*
trie tree的储存方式：将字母储存在边上，边的节点连接与它相连的字母
trie[rt][x]=tot:rt是上个节点编号，x是字母，tot是下个节点编号
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define maxn 2000010
using namespace std;
int tot=1,n;
int trie[maxn][26];
//bool isw[maxn];查询整个单词用
void insert(char *s,int rt)
{
for(int i=0;s[i];i++)
{
int x=s[i]-'a';
if(trie[rt][x]==0)//现在插入的字母在之前同一节点处未出现过
{
trie[rt][x]=++tot;//字母插入一个新的位置，否则不做处理
}
rt=trie[rt][x];//为下个字母的插入做准备
}
/*isw[rt]=true;标志该单词末位字母的尾结点，在查询整个单词时用到*/
}
bool find(char *s,int rt)
{
for(int i=0;s[i];i++)
{
int x=s[i]-'a';
if(trie[rt][x]==0)return false;//以rt为头结点的x字母不存在，返回0
rt=trie[rt][x];//为查询下个字母做准备
}
return true;
//查询整个单词时，应该return isw[rt]
}
char s[22];
int main()
{
tot=0;
int rt=1;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>s;
insert(s,rt);
}
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>s;
if(find(s,rt))printf("YES\n");
else printf("NO\n");
}
return 0;
}
判断一个数出现的次数
查询前缀出现的次数
#include #include #include #include using namespace std;int trie[400001][26],len,root,tot,sum[400001];bool p;int n,m; char s[11];void insert(){ len=strlen(s); root=0; for(int i=0;i >s; insert(); } scanf("%d",&m); for(int i=1;i<=m;i++) { cin>s; printf("%d\n",search()); }}