Trie树就是字典树，其核心思想就是空间换时间。
举个简单的例子。
给你100000个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，第一次出现第几个位置。
这题当然可以用hash来，但是我要介绍的是trie树。在某些方面它的用途更大。比如说对于某一个单词，我要询问它的前缀是否出现过。这样hash就不好搞了，而用trie还是很简单。
现在回到例子中，如果我们用最傻的方法，对于每一个单词，我们都要去查找它前面的单词中是否有它。那么这个算法的复杂度就是O(n^2)。显然对于100000的范围难以接受。现在我们换个思路想。假设我要查询的单词是abcd，那么在他前面的单词中，以b，c，d，f之类开头的我显然不必考虑。而只要找以a开头的中是否存在abcd就可以了。同样的，在以a开头中的单词中，我们只要考虑以b作为第二个字母的……这样一个树的模型就渐渐清晰了……
假设有b，abc，abd，bcd，abcd，efg，hii这6个单词，我们构建的树就是这样的。
对于每一个节点，从根遍历到他的过程就是一个单词，如果这个节点被标记为红色，就表示这个单词存在，否则不存在。
那么，对于一个单词，我只要顺着他从跟走到对应的节点，再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色，就相当于插入了这个单词。
这样一来我们询问和插入可以一起完成，所用时间仅仅为单词长度，在这一个样例，便是10。
我们可以看到，trie树每一层的节点数是26^i级别的。所以为了节省空间。我们用动态链表，或者用数组来模拟动态。空间的花费，不会超过单词数×单词长度。
模版一：
/*******************************************************************************
【字典树】
此模板主要是针对都是小写字母的。其他情况在此基础上改一改就可以了，要懂得灵活运用。
********************************************************************************/
struct trie /*字典树的节点内容*/
{
int count;/*计算该节点出现的次数*/
trie *next[26];/*一个节点有26个指针（孩子），即'a'-'z'*/
};
trie *root;
trie* newtrie()/*建立一个节点。（也可以用建立个大的数组，指针指向数组不同位置）*/
{
trie *t;
t=(trie*)malloc(sizeof(struct trie));
memset(t,0,sizeof(struct trie));
return t;
}
void Insert(char *ch) /*插入函数，将该字符串插入到字典树中 */
{
int i;
trie *t,*s;
s=root;
for(i=0;ch[i];i++)
{
if(s->next[ch[i]-'a'])
{
s=s->next[ch[i]-'a'];
s->count=s->count+1;
}
else
{
t=newtrie();
s->next[ch[i]-'a']=t;
s=t;
s->count=1;
}
}
}
int Search(char *ch)/*搜索函数，返回0则代表字典树不存在该字符串，反之亦然 */
{
int i;
trie *s=root;
if(ch[0]==0) return 0;
for(i=0;ch[i];i++)
{
if(s->next[ch[i]-'a'])
s=s->next[ch[i]-'a'];
else
break;
}
if(ch[i]==0) return s->count;
else return 0;
}
void Delete(char *ch)/*删除函数，将该字符串从字典树中删除（删除之前记得事先判断存不存在该字符串）*/
{
int i;
trie *s;
s=root;
for(i=0;ch[i];i++)
{
s=s->next[ch[i]-'a'];
s->count=s->count-1;
}
}
模板二：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
//字典树的数据结构
struct Trie{
Trie *child[26];//这里数组的大小看是小写字母还是数字还是都有
int num;
Trie(){//初始化
num = 0;
memset(child , 0 , sizeof(child));
}
};
Trie *root;
//字典树的构建
void Tree_Insert(char *str){
Trie *s = root;
int i = 0;
while(str[i]){
int id = str[i] -'a' ;
if(s -> child[id] == 0)//如果该字节点的字节点为空则要创建中间节点
s -> child[id] = new Trie();
s = s -> child[id];
s -> num++;
i++；
}
}
//字典树的查找
int Tree_Find(char *str){
Trie *s = root;
int count ;
while(str[i]){
int id = str[i] - 'a';
if(s -> child[id] == 0){//如果当前指针s的对应于当前字符str[i]在字母表的位置的子节点为空
return count;//直接返回0
}
else{
s = s -> child[id];
count = s -> num ;
}
i++;
}
return count;
}
int main(){
int i , j;
//建立一个root分配空间
root = new Trie();
return 0;
}