首页 > 代码库 > Trie树的简单描述（需后续总结）
Trie树的简单描述（需后续总结）
http://www.cnblogs.com/pony1993/archive/2012/07/18/2596730.html
它有三个基本性质，根节点不包含字符，除根节点外每一个节点都只包含一个字符，从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串，每个节点的所有子节点包含的字符都不相同。
1. 从根节点开始一次搜索
2. 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索
3. 在相应的子树上，取得要查找关键词的第二个字母，并进一步选择对应的子树进行检索
4. 迭代过程...
5. 在某个节点处，关键词的所有字母已被取出，则读取附在该节点上的信息，即完成查找
字典树的应用
1.字典树在串的快速检索中的应用。
给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。
在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。
2. 字典树在“串”排序方面的应用
给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出
用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可
3. 字典树在最长公共前缀问题的应用
对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为最近公共祖先问题。
字典树的基本功能是用来查询某个单词（前缀）在所有单词中出现次数的一种数据结构，它的插入和查询复杂度都为O(len),Len为单词（前缀）长度，但是它的空间复杂度却非常高，如果字符集是26个字母，那每个节点的度就有26个，典型的以空间换时间结构。
基本模版
1、结构体定义：
2、新节点建立
3、插入
4、查找
杭电模版题 HDU 1247 Hat‘s Words http://acm.hdu.edu.cn/showproblem.php?pid=1247
1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 const int N=26;
5 const int maxn=1000000;
6 char s[50001][101];
7 using namespace std;
8 struct node
9 {
10 int flag;
11 int count;
12 struct node *next[N];
13 }tree[maxn];
14 int t=0;
15 struct node *creat()
16 {
17 int i;
18 struct node *p;
19 p=&tree[t++];
20 p->count=1;
21 p->flag=0;
22 for(i=0;i<N;i++)
23 {
24 p->next[i]=NULL;
25 }
26 return p;
27 }
28 void insert(struct node **root,char *s)
29 {
30 int i,k;
31 struct node *p;
32 if(!(p=*root))
33 {
34 p=*root=creat();
35 }
36 i=0;
37 while(s[i])
38 {
39 k=s[i++]-‘a‘;
40 if(p->next[k])
41 p->next[k]->count++;
42 else
43 p->next[k]=creat();
44 p=p->next[k];
45 }
46 p->flag=1;
47 }
48 int search(struct node **root,char *s)
49 {
50 int i=0,k;
51 struct node *p;
52 if(!(p=*root))
53 {
54 return 0;
55 }
56 while(s[i])
57 {
58 k=s[i++]-‘a‘;
59 if(!(p->next[k]))
60 return 0;
61 p=p->next[k];
62 }
63 return p->flag;
64 }
65 int main()
66 {
67 char s1[101],s2[101],s3[101];
68 int l,i,j,k,c=0;
69 struct node *root=NULL;
70 while(~scanf("%s",s[c]))
71 {
72 insert(&root,s[c]);
73 c++;
74 }
75 for(i=0;i<c;i++)
76 {
77 memset(s1,0,sizeof(s1));
78 l=strlen(s[i]);
79 for(j=0;j<l;j++)
80 {
81 s1[j]=s[i][j];
82 if(search(&root,s1))
83 {
84 memset(s2,0,sizeof(s2));
85 for(k=j+1;k<l;k++)
86 s2[k-j-1]=s[i][k];
87 if(search(&root,s2))
88 {
89 puts(s[i]);
90 break;
91 }
92 }
93 }
94 }
95 return 0;
96
HDU 1075 What Are You Talking About
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 using namespace std;
6 const int N=26;
7 const int maxn=3007;
8 struct node
9 {
10 int flag;
11 char t[11];
12 struct node *next[N];
13 };
14 struct node *creat()
15 {
16 int i;
17 struct node *p=new (struct node);
18 p->flag=0;
19 for(i=0;i<N;i++)
20 {
21 p->next[i]=NULL;
22 }
23 return p;
24 }
25 void insert(struct node **root,char *s,char *s1)
26 {
27 int i,k;
28 struct node *p;
29 if(!(p=*root))
30 {
31 p=*root=creat();
32 }
33 i=0;
34 while(s[i])
35 {
36 k=s[i++]-‘a‘;
37 if(p->next[k]==NULL)
38 p->next[k]=creat();
39 p=p->next[k];
40 }
41 p->flag=1;
42 strcpy(p->t, s1);
43 }
44 int search(struct node **root,char *s,char *s1)
45 {
46 int i=0,k;
47 struct node *p;
48 if(!(p=*root))
49 {
50 return 0;
51 }
52 while(s[i])
53 {
54 k=s[i++]-‘a‘;
55 if(!(p->next[k]))
56 return 0;
57 p=p->next[k];
58 }
59 if(p->flag)
60 {
61 strcpy(s1, p->t);
62 return 1;
63 }
64 return 0;
65 }
66 int main()
67 {
68 int i,j,l,k,len;
69 struct node *root=NULL;
70 char s[11],s1[11],s2[11];
71 while(~scanf("%s",s))
72 {
73 if(!strcmp(s,"END"))
74 break;
75 if(strcmp(s,"START"))
76 {
77 scanf("%s",s2);
78 insert(&root,s2,s);
79 }
80 }
81 getchar();
82 char line[maxn];
83 while(gets(line))
84 {
85 if(!strcmp(line,"END"))
86 break;
87 if(strcmp(line,"START"))
88 {
89 len=strlen(line);
90 k=0;
91 memset(s,0,sizeof(s));
92 for(i=0;i<len;i++)
93 {
94
95 if(islower(line[i]))
96 {
97 s[k++]=line[i];
98 if(i==len-1)
99 {
100 memset(s1,0,sizeof(tm));
101 if(search(&root,s,s1))
102 {
103 l=strlen(s1);
104 for(j=0;j<l;j++)
105 printf("%c",s1[j]);
106 }
107 else
108 {
109 for(j=0;j<k;j++)
110 printf("%c",s[j]);
111 }
112 break;
113 }
114 }
115 else
116 {
117 memset(s1,0,sizeof(s1));
118 if(search(&root,s,s1))
119 {
120 l=strlen(s1);
121 for(j=0;j<l;j++)
122 printf("%c",s1[j]);
123 }
124 else
125 for(j=0;j<k;j++)
126 printf("%c",s[j]);
127 printf("%c",line[i]);
128 k=0;
129 memset(s,0,sizeof(s));
130 }
131 }
132 puts("");
133 }
134 memset(line,0,sizeof(line));
135 }
136 return 0;
137 }
138
POJ模版题 POJ 3630 Phone List http://poj.org/problem?id=3630
1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 const int N=11;
5 const int maxn=1000001;
6 int flag;
7 using namespace std;
8 struct node
9 {
10 int flag;
11 int count;
12 struct node *next[N];
13 }tree[maxn];
14 int t=0;
15 struct node *creat()
16 {
17 int i;
18 struct node *p;
19 p=&tree[t++];
20 p->count=1;
21 p->flag=0;
22 for(i=0;i<N;i++)
23 {
24 p->next[i]=NULL;
25 }
26 return p;
27 }
28 void insert(struct node **root,char *s)
29 {
30 int i,k,l;
31 struct node *p;
32 if(!(p=*root))
33 {
34 p=*root=creat();
35 }
36 l=strlen(s);
37 for(i=0;i<l;i++)
38 {
39 k=s[i]-‘0‘;
40 if(p->next[k]&&i==l-1)
41 {
42 flag=1;
43 return;
44 }
45 if(p->next[k])
46 {
47 if(p->next[k]->flag)
48 {
49 flag=1;
50 return;
51 }
52 }
53 else
54 p->next[k]=creat();
55 p=p->next[k];
56 }
57 p->flag=1;
58 }
59 int search(struct node **root,char *s)
60 {
61 int i=0,k;
62 struct node *p;
63 if(!(p=*root))
64 {
65 return 0;
66 }
67 while(s[i])
68 {
69 k=s[i++]-‘0‘;
70 if(!(p->next[k]))
71 return 0;
72 p=p->next[k];
73 }
74 return p->flag;
75 }
76 int main()
77 {
78 char s1[N];
79 int t,i,c;
80 scanf("%d",&t);
81 while(t--)
82 {
83 flag=0;
84 struct node *root=NULL;
85 scanf("%d%*c",&c);
86 for(i=0;i<c;i++)
87 {
88 scanf("%s",s1);
89 if(!flag)
90 {
91 insert(&root,s1);
92 }
93 }
94 if(flag)
95 puts("NO");
96 else
97 puts("YES");
98 }
99 return 0;
100 }
101
Trie树的简单描述（需后续总结）