利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的
上图是由
构成的字典树。每个节点代表的单词是从根遍历到他的路径，标黄的是当前节点存在单词
代码实现：
struct Trie{ Trie *son[26]; bool w;//记录当前节点是否是单词； }root;
对于一个单词，我只要按照它的每个字母从根走到对应的节点，再看这个节点是否被标记为黄色就可以知道它是否出现过了。
如果没被标记，把这个节点标记为红色，就相当于插入了这个单词，这样查找和插入就可以一起实现。
代码实现：
void search(char s[]){//查找和插入 Trie *x=&root; for(int i=0;s[i];i++){ if(x->son[s[i]-‘a‘]==NULL){//判断之前是否出现过 x->son[s[i]-‘a‘]=new Trie;//创建新的节点 } x=x->son[s[i]-‘a‘]; } if(!x->w)sum++,x->w=1;//sum总结点数+1 }
void trie_free(Trie* x){//空间释放 for(int i=0;i<26;i++){ if(x->son[i]!=NULL)trie_free(x->son[i]);//先释放子节点 } delete x; }
原文：http://www.cnblogs.com/bennettz/p/7636021.html