字典树，又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。 典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常 被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存 储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。 字典树与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一 个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字 母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样 的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据。 好了废话不多说直接看代码：
/*1、查询是否出现 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; } //2、查询前缀出现次数 #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> 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<len;i++) { int id=s[i]-'a'; if(!trie[root][id]) trie[root][id]=++tot; sum[trie[root][id]]++;//前缀保存 root=trie[root][id]; } } int search() { root=0; len=strlen(s); for(int i=0;i<len;i++) { int id=s[i]-'a'; if(!trie[root][id]) return 0; root=trie[root][id]; }//root经过此循环后变成前缀最后一个字母所在位置 return sum[root]; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { cin>>s; insert(); } scanf("%d",&m); for(int i=1;i<=m;i++) { cin>>s; printf("%d\n",search()); } }