Trie_tree

发表于   |   分类于

##基本算法学习笔记之Trie树

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

简单C代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <stdio.h>
#include <stdlib.h>
#define MAX 26
#define bool int
#define false 0
#define true 1
typedef struct TrieNode
{
    bool isStr;               //判断是否是一个单词时用到
	int count;               //当前节点前缀相同的单词数
	struct TrieNode *next[MAX];
}Trie;
void Insert(Trie *root, const char *s)
{
    if (root == NULL || *s == '\0')
        return ;
    int i;
    Trie *p = root;
    int t;
    while (*s != '\0')
    {
        t = *s - 'a';
        if (p->next[t] == NULL)
        {
            Trie *temp = (Trie*)malloc(sizeof(Trie));
            for (i=0; i< MAX; i++)
                temp->next[i] = NULL;
            temp->isStr = false;
            temp->count = 0;
            p->next[t] = temp;
        }
        p = p->next[t];  
        p->count++;
        s++;
    }
    p->isStr = true;
}
int Search(Trie *root, const char *s)
{
    Trie *p = root;
    while (p != NULL && *s != '\0')
    {
        p = p->next[*s-'a'];
        s++;
    }
    return (p != NULL);
}
int prefixnum(Trie *root, const char *s)
{
    Trie *p = root;
    int t;
    while (p != NULL && *s != '\0')
    {
        t = *s - 'a';
        if (p->next[t] == NULL)
            return 0;
        p = p->next[t];
        s++;
    }
    return p->count;
}
void del(Trie *root)
{
    int i;
    for (i=0; i<MAX; i++)
    {
        if (root->next[i] != NULL)
        {
            del(root->next[i]);
        }
    }
    free(root);
}
int main()
{
    int i;
    int n,m;  //n为建立Trie树输入的单词数，m为要查找的单词数
    char s[100];
    int *cum;
    Trie *root = (Trie*)malloc(sizeof(Trie));
    for (i=0; i<MAX; i++)
    {
        root->next[i] = NULL;
    }
    root->isStr = false;
    root->count = 0;
    scanf("%d", &n);
    getchar();
    for (i=0; i< n; i++)
    {
        scanf("%s", s);
        Insert(root, s);
    }
    scanf("%d", &m);
    cum = (int*)malloc(sizeof(int)*m);
    for (i=0; i<m; i++)
    {
        scanf("%s", s);
        *(cum+i) = prefixnum(root, s);
    }
    for (i=0; i<m; i++)
    {
        printf("%d\n", *(cum+i));
    }
    free(cum);
    del(root);
    return 0;
}

可以看出明显很费空间，优化等有空再研究了。
参考链接
(http://www.cnblogs.com/dolphin0520/archive/2011/10/11/2207886.html)

练习题
(http://hihocoder.com/problemset/problem/1014)