字典树(基本模版+操作)

字典树，又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

字典树与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据。

好了，废话不多说，下面看其定义和操作。

数据结构的定义如下：

1 #define MAXN 10
2 
3 typedef struct Trie
4 {
5   Trie *next[MAXN];
6   int v;
7 }Trie;
8 
9 Trie *root;

1、先说一下root。root是整棵字典树的根，其中不存放任何与输入的字符串有关的信息，它的子结点才是输入字符串的第一个字符--str[0]...

2、每个结点的最大分支数MAXN根据要求变化，如果输入的是数字(0~9)的组合，定义为10就ok，若是小写字母则定义为26，大小写字母定义为52...

3、其中的v比较灵活，用于保存一些信息，具体是什么信息根据题目具体要求具体变化，如：可以定义为以从root到此结点的结点组合为前缀的字符串的个数，可以用来记录此结点是否为某个字符串的尾结点...

4、对于root的定义一般也有两种写法：Trie root; 或者 Trie *root;　　第一种一般用于一个题目只有一棵字典树的情况，第二种主要用于题目中需要动态建立多棵字典树进行处理的时候(便于清空已经使用过的Trie内存)，在main()中要root = malloc(sizeof(Trie));

字典树建立过程

1、依次读取字符串的每个字符...

2、建树过程中，需要两个temp指针，*p 和 *q，*p 用于从根节点开始(Trie *p = root;若前面定义root时用的是第二种方式，则此处为Trie *p = &root;)依次往下找，每次都选择str[i]所在的子树，若str[i]已经存在则p=p->next[id]，若不存在则用*q建立一个新结点，将其插到P->next[]中(若对v有操作，此时也同时进行)...

3、在读取字符串每个字符的for循环结束后，一棵其中只包含了一个字符串信息的字典树就建成了...

4、对每个要加入到树中的字符串依次调用此函数...

模版如下：

 1 void createTrie(char *str)
 2 {
 3     int len = strlen(str);
 4     Trie *p = root, *q;
 5     for(int i=0; i<len; ++i)
 6     {
 7         int id = str[i]-'0';
 8         if(p->next[id] == NULL)
 9         {
10             q = (Trie *)malloc(sizeof(Trie));
11             q->v = 0;    //对v的初始化
12             for(int j=0; j<MAX; ++j)
13                 q->next[j] = NULL;
14             p->next[id] = q;
15             p = p->next[id];
16         }
17         else
18         {19             p = p->next[id];
20         }
21     }
22     /*code*/
23 }

1、若是字母的字典树，第7行代码改为 int id = str[i] - 'a';

2、其中对于v的操作具体变化

查找过程

(1) 每次从根结点开始一次搜索；
(2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；　　

(3) 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。　　

(4) 迭代过程…… 　　
(5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。

模版如下：

 1 int findTrie(char *str)
 2 {
 3   Trie *p = &root;
 4   for (int i = 0; i < strlen(str); ++i)
 5   {
 6     int id = str[i] - 'a';
 7     if (p->next[id] == NULL)
 8     {
 9       return 0;
10     }else
11     {
12       p = p->next[id];
13     }
14   }
15   return p->v;
16 }

这个是用于处理以str为前缀的字符串的数目的...

删除--释放内存

我们可以看到，其实字典树的空间开销是比较大的，尤其是动态建立了多棵字典树的时候，所以在题目上的内存有限制的情况下，我们有必要在使用完一棵字典树时将其内存释放，代码如下：

 1 int dealTrie(Trie* T)
 2 {
 3     int i;
 4     if(T==NULL)
 5         return 0;
 6     for(i=0;i<MAX;i++)
 7     {
 8         if(T->next[i]!=NULL)
 9             deal(T->next[i]);
10     }
11     free(T);
12     return 0;
13 }

到此一棵字典树的基本操作就完成了。

1、HDOJ 1251 统计难题

http://acm.hdu.edu.cn/showproblem.php?pid=1251

2、HDOJ 1671 Phone List

http://acm.hdu.edu.cn/showproblem.php?pid=1671

3、想深入研究的童鞋可以看看这篇字典树的文章 PDF ：算法合集之《浅析字母树在信息学竞赛中的应用》

http://pan.baidu.com/s/16dkSY

这是上面两题的AC代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #define MAXL 15
 5 #define MAXN 30
 6 
 7 typedef struct Trie
 8 {
 9   Trie *next[MAXN];
10   int v;
11 }Trie;
12 
13 Trie root;
14 
15 int createTrie(char *str)
16 {
17   Trie *p = &root, *q;
18   for (int i = 0; i < strlen(str); ++i)
19   {
20     int id = str[i] - 'a';
21     if (p->next[id] == NULL)
22     {
23       q = (Trie*)malloc(sizeof(Trie));
24       q->v = 1;
25       for (int j = 0; j < MAXN; ++j)
26       {
27         q->next[j] = NULL;
28       }
29       p->next[id] = q;
30       p = p->next[id];
31     }else
32     {
33       p->next[id]->v++;
34       p = p->next[id];
35     }
36   }
37   return 0;
38 }
39 
40 int findTrie(char *str)
41 {
42   Trie *p = &root;
43   for (int i = 0; i < strlen(str); ++i)
44   {
45     int id = str[i] - 'a';
46     if (p->next[id] == NULL)
47     {
48       return 0;
49     }else
50     {
51       p = p->next[id];
52     }
53   }
54   return p->v;
55 }
56 
57 int main()
58 {
59   char line[MAXL];
60   while(gets(line) && line[0] != '')
61   {
62       createTrie(line);
63   }
64   memset(line, 0, sizeof(line));
65   while(scanf("%s", &line) != EOF)
66   {
67     printf("%d
", findTrie(line));
68   }
69   return 0;
70 }

View Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #define MAXN 10
  5 
  6 typedef struct Trie
  7 {
  8   Trie *next[MAXN];
  9   int v;
 10 }Trie;
 11 
 12 Trie *root;
 13 
 14 int createTrie(char *str)
 15 {
 16   Trie *p = root, *q;
 17   for (int i = 0; i < strlen(str); ++i)
 18   {
 19     int id = str[i] - '0';
 20     if (p->next[id] == NULL)
 21     {
 22       q = (Trie*)malloc(sizeof(Trie));
 23       q->v = 0;
 24       for (int j = 0; j < MAXN; ++j)
 25       {
 26         q->next[j] = NULL;
 27       }
 28       p->next[id] = q;
 29       p = p->next[id];
 30     }
 31     else
 32     {
 33       if (p->next[id]->v == -1)
 34       {
 35         return 0;
 36       }
 37       p = p->next[id];
 38     }
 39   }
 40   p->v = -1;
 41   for (int i = 0; i < MAXN; ++i)
 42   {
 43     if (p->next[i] != NULL)
 44     {
 45       return 0;
 46     }
 47   }
 48   return 1;
 49 }
 50 
 51 int deleteTrie(Trie *T)
 52 {
 53   if (T == NULL)
 54   {
 55     return 0;
 56   }else
 57   {
 58     for (int i = 0; i < MAXN; ++i)
 59     {
 60       if(T->next[i] != NULL)
 61       {
 62       deleteTrie(T->next[i]);
 63       }
 64     }
 65   }
 66   free(T);
 67   return 0;
 68 }
 69 
 70 int main()
 71 {
 72   int T,N; 
 73   char line[MAXN];
 74   scanf("%d", &T);
 75   while(T--)
 76   {
 77     root = (Trie*)malloc(sizeof(Trie));
 78     for(int i = 0; i < MAXN; i++)
 79     {
 80       root->next[i] = NULL;
 81     }
 82     int flag = 1;
 83     scanf("%d", &N);
 84     for (int i = 0; i < N; ++i)
 85     {
 86       scanf("%s", &line);
 87       int a = createTrie(line);
 88       if (a == 0)
 89       {
 90         flag = 0;
 91       }
 92     }
 93     if (flag)
 94     {
 95       printf("YES
");
 96     }else
 97     {
 98       printf("NO
");
 99     }
100     deleteTrie(root);
101   }
102   return 0;
103 }

View Code