字典树：又称为Trie，是一种用于快速检索的多叉树结构，
字典树（Trie）
。Trie把要查找的关键词看作一个字符序列，并根据构成关键词字符的先后顺序构造用于检索的树结构；一棵m度的Trie树或者为空，或者由m棵m度的Trie树构成。注意：和二叉查找树不同的是，其节点并非存储一个元素。
优点：1、利用公共内存，以达到节约内存的目的
2、根节点只存储其子树，不存储字母
3、每个节点代表的字母都不同
基本定义：
typedef struct Node{ struct Node*child[26]; int n; //根据题意变化}Trie;时间复杂度：㏒n（虽然与二叉查找树的复杂度同为㏒n，但是其效率略优于二叉查找树）
字典树的结构示意：
相关题目：
hdu1251统计难题
hdu1075 What Are You Talking About
hdu1298 T9
hdu1800 Flying to the Mars
zoj 1109 Language of FatMouse
字典树实例：hdu1251统计难题
这是一道十分经典的字典树问题，但是这里大家在提交代码是一定要注意编译器的选择，如果选择g++的话，那么一定是爆内存的，所以提交的一定要选择C++。为什么呢，因为g++是64位版本的编译器，c++是32位的。也就是说同样多的指针，g++是c++的两倍。当然关于这个问题，仅限于hdu。之前我就是用g++上交，然后问题就来了，一直爆内存。最后知道还有这么一回事，然后才AC。白白浪费我一个晚上的时间来改错啊，说多了都是泪啊。
<span>#include<stdio.h>#include<string.h>#include<stdlib.h>typedef struct Node{ Node *child[26]; int cnt;}Trie;Trie* root; //定义根节点Trie* addnode(){ //申请新的节点空间并初始化 Trie* u = (Trie*)malloc(sizeof(Trie)); for(int i = 0; i < 26; i++){ u->child[i] = NULL; } return u;}void remove_tree(Trie* u){ //释放内存，一定要注意！！！ if(u == NULL) return ; for(int i = 0; i < 26; i++) remove_tree(u->child[i]); free(u); u = NULL; return ;}void Insert(char *s){ //插入字符串，并计数 Trie* u = root; for(int i = 0; i < strlen(s); i++){ if(u->child[s[i]-'a'] == NULL){ Trie* newnode = addnode(); u->child[s[i]-'a'] = newnode; u = newnode; u->cnt = 1; }else{ u = u->child[s[i]-'a']; u->cnt = u->cnt + 1; } }}int find(char *s){ //查找字符串 Trie* u = root; for(int i = 0; i < strlen(s); i++){ if(u->child[s[i]-'a']!=NULL) u = u->child[s[i]-'a']; else return 0; } return u->cnt;}int main(){ int n; char s[15]; root = addnode(); //创建根节点 root->cnt = 0; //进行初始化 while(gets(s),strcmp(s,"")) Insert(s); //树的构建 while(scanf("%s",s)!=EOF){ n = find(s); printf("%d\n",n); } remove_tree(root); //释放内存 return 0;}</stdlib.h></string.h></stdio.h></span>