字典树：顾名思义就是按照字典排序方法所创建的树
下面以一个经典的字典树例题进行讲解：
hiho一下第二周 Hihocoder #1014 : Trie树
描述
小Hi和小Ho是一对好朋友，出生在信息化社会的他们对编程产生了莫大的兴趣，他们约定好互相帮助，在编程的学习道路上一同前进。
这一天，他们遇到了一本词典，于是小Hi就向小Ho提出了那个经典的问题：“小Ho，你能不能对于每一个我给出的字符串，都在这个词典里面找到以这个字符串开头的所有单词呢？”
输入
输入的第一行为一个正整数n，表示词典的大小，其后n行，每一行一个单词（不保证是英文单词，也有可能是火星文单词哦），单词由不超过10个的小写英文字母组成，可能存在相同的单词，此时应将其视作不同的单词。接下来的一行为一个正整数m，表示小Hi询问的次数，其后m行，每一行一个字符串，该字符串由不超过10个的小写英文字母组成，表示小Hi的一个询问。
在20%的数据中n, m<=10，词典的字母表大小<=2.
在60%的数据中n, m<=1000，词典的字母表大小<=5.
在100%的数据中n, m<=100000，词典的字母表大小<=26.
本题按通过的数据量排名哦～
输出
对于小Hi的每一个询问，输出一个整数Ans,表示词典中以小Hi给出的字符串为前缀的单词的个数。
- 样例输入
-
5 babaab babbbaaaa abba aaaaabaa babaababb 5 babb baabaaa bab bb bbabbaab
- 样例输出
-
1 0 3 0 0
简单分析：
其实原文里面思路解释的非常清楚，But the most important is no code！
这里主要的问题是该如何将单词储存起来并且每次询问都能快速找到答案。没错答案就是树！
利用链表的灵活性创建树简直完美，效率也非常高，话不多说，Look code（this is important）
1 #include <stdio.h> 2 using namespace std; 3 4 #define maxn 30 5 6 //首先定义一个结构体，目的是为了存放整个树 7 struct Node{ 8 int num; 9 Node *next[maxn]; 10 //初始化结构体 11 Node(){ 12 num=0; 13 for(int i = 0;i < maxn;i++){ 14 next[i]=NULL; 15 } 16 } 17 } N; 18 19 //创建树（关键!) 20 void add(char x[]){ 21 //将树的地址传入，目的是创建新树，注意传入的必须是地址！ 22 Node *p=&N; 23 for(int i = 0;x[i];i++){ 24 int xx=x[i]-'a'; 25 //如果该节点下没有对应的分支创建一个新的分支 26 if(p->next[xx]==NULL) 27 p->next[xx]=new Node; 28 //延伸链表 29 p=p->next[xx]; 30 //记录走过该节点的次数 31 p->num++; 32 } 33 } 34 35 //查找树 36 int findn(char x[]){ 37 //同样是传地址进去，目的是在树中查找 38 Node *q=&N; 39 for(int i=0;x[i];i++){ 40 int xx=x[i]-'a'; 41 //树中如果没有对应的说明没有找到 42 if(q->next[xx]==NULL) 43 return 0; 44 else 45 q=q->next[xx]; 46 } 47 return q->num; 48 } 49 50 int main(){ 51 int n,m; 52 char str[30]; 53 scanf("%d",&n); 54 for(int i=0;i<n;i++){ 55 scanf("%s",str); 56 add(str); 57 } 58 scanf("%d",&m); 59 for(int i = 0;i < m;i++){ 60 scanf("%s",str); 61 printf("%d ",findn(str)); 62 } 63 return 0; 64 }
------------------------------------------------------------------------------------------------------------------------------------------------------------
啦啦啦啦啦啦啦啦啊啦啦啦啦啦啦啦啦啦啦，又一次看到我的字典树模板，有必要更新一下，不断学习才能有进步
1 #include <iostream> 2 using namespace std; 3 const int maxn = 1e5+10; 4 char str[20]; 5 int n, m, num = 1, tree[maxn*4][30], sum[maxn*4]; 6 void add(){ 7 for(int i = 0, node = 0; str[i]; i++){ 8 int xx = str[i] - 'a'; 9 if(!tree[node][xx]) tree[node][xx] = num++; 10 sum[tree[node][xx]]++; 11 node = tree[node][xx]; 12 } 13 } 14 int query(){ 15 int node = 0; 16 for(int i = 0; str[i]; i++){ 17 int xx = str[i] - 'a'; 18 if(!tree[node][xx]) return 0; 19 node = tree[node][xx]; 20 } 21 return sum[node]; 22 } 23 int main(){ 24 scanf("%d", &n); 25 while(n--){ 26 scanf("%s", str); 27 add(); 28 } 29 scanf("%d", &m); 30 while(m--){ 31 scanf("%s", str); 32 cout<<query()<<endl; 33 } 34 return 0; 35 }
------------------------------------------------------------------------------------------------------------------------------------------------------------
只有不断学习才能进步！