字典树：又叫trie树，单词查找树。是一种树形结构，典型的用于统计。经常用于统计一片文章当中出现确定的单词的次数，它的优点就在于：省略了相同前缀的比较。以下图为例：用单词carbohy,carhure,english,englnee来构造的trie树。
当你用trie树来查找一个单词的时候，就像查字典是一样的，先查第一个单词，然后查第二个，在树中我们用深度遍历就可以实现。当然你不一定存储字母也可以存储数字什么的，根据具体情况来选择。
trie树结构定义：
-
typedef struct node
-
{
-
int cnt;
-
node* next[26];
-
} Trie;
next数组视情况而定，如果既有小写又有大写就是52，如果还有数字则更多。
接着就是构造trie树了，根据提供的单词构造trie树
过程如下：（跟树的构造类似）
-
void Creat_Trie(char*str){
-
int len,i,j;
-
len=strlen(str);
-
Trie *p=&root,*q;
-
for( i=0; i<len; i++){
-
int id=str[i]-‘a‘;
-
if( p->next[id]==NULL){
-
q=new Trie;
-
q->cnt=1;
-
for( j=0; j<26; j++)
-
q->next[j]=NULL;
-
p->next[id]=q;
-
p=p->next[id];
-
}
-
else{
-
p->next[id]->cnt++;
-
p=p->next[id];
-
}
-
}
-
}
构造trie树之后查找，这也是trie树重要的功能。
-
int Find_Trie(char*str){
-
int len,i,j,id;
-
len=strlen(str);
-
Trie*p=&root;
-
for( i=0; i<len; i++){
-
id=str[i]-‘a‘;
-
p=p->next[id];
-
if( p==NULL)
-
return 0;
-
}
-
return p->cnt;
题目：入门--统计难题hdu
