算法笔记 - Trie树

| | |

Trie树，又称字典树、单词查找树，是一种树形结构，利用字符串的公共前缀来减少查询时间，最大限度地减少无谓地字符串比较，在统计和处理大量数据方面运用广泛，常用于搜索引擎词频统计。

Trie

上图是一棵最基本的字典树，如果将树的根结点到每一个子结点所经过的路径上的字母连起来，就构成了字典中的一个个单词，这棵树就形成了一本字典。每个结点分别包含下一个字母结点的指针，以及从根结点到该结点的路径是否是一个单词的标志，黑色结点表示可构成一个单词，还可包含在建树过程中经过该结点的次数，这个次数用于表示字典中以根结点到该结点所构成的单词为前缀的单词个数。

以英文单词字典树为例，每个结点最多包含26个子结点，因为总共有26个字母（全为小写）。则Trie树的结点可用以下结构体表示：

1
2
3
4
5
6
typedef struct TrieNode
{
    bool isStr;    //表示是否能构成单词
    int l;    //以根结点到此结点构成的单词为前缀的单词数
    struct TrieNode *next[26];    //共26个子节点
}Trie;

查询以输入字段为前缀的单词数的实现过程：

首先输入一个正整数n, 表示字典单词数，然后分别输入n个单词来构建字典数，接下来输入一个正整数m，表示要查找的次数，并依次输入要查询的前缀，程序会输出以各个字段为前缀的单词数量。

以下是程序代码：

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

#include<iostream>
#include<cstdlib>
#define MAX 26
using namespace std;

typedef struct TrieNode
{
    bool isStr;
    int l;
    struct TrieNode *next[MAX];
}Trie;

//向树中插入单词
void insert(Trie *root,const char *s)
{
    if(root==NULL || *s=='\0') return;

    Trie *p = root;
    int i=0;

    while(*s!='\0')
    {
        if(p->next[*s-'a']==NULL)
        {
            Trie *temp = (Trie *)malloc(sizeof(Trie));
            temp->isStr = false;
            temp->l=1;
            for(i=0;i<MAX;i++)
            {
                temp->next[i] = NULL;
            }

            p->next[*s-'a'] = temp;
            p=p->next[*s-'a'];
        }
        else
        {
            p=p->next[*s-'a'];
            p->l++;
        }
        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 ? 0 : p->l;
}

//删除整棵树并释放空间
void del(Trie *root)
{
    Trie *p = root;
    for(int i=0;i<MAX;i++)
    {
        if(p->next[i]!=NULL)
        {
            del(p->next[i]);
        }
    }
    free(p);
}


int main()
{
    int n;  //字典中单词树
    int m;  //查询数目
    int i;
    char word[100]; //单词缓冲区

    //初始化字典树
    Trie *root = (Trie *)malloc(sizeof(Trie));
    for(i=0;i<MAX;i++)
    {
        root->next[i] = NULL;
    }
    root->isStr=false;

    scanf("%d",&n);
    getchar();

    for(i=0;i<n;i++)
    {
        scanf("%s",word);
        insert(root,word);
    }

    scanf("%d",&m);
    getchar();
    int result[100];    //查询结果集

    for(i=0;i<m;i++)
    {
        scanf("%s",word);
        result[i] = search(root,word);
    }
    del(root);

    //输出结果
    for(i=0;i<m;i++)
    {
        printf("%d\n",result[i]);
    }
    system("PAUSE");
    return 0;
}

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
5
apple
application
cat
add
catch
5
app
cat
a
add
apple

样例输出

1
2
3
4
5
2
2
3
1
1

本文为作者kMacro原创，转载请注明来源：https://zkhdev.github.io/2017/03/02/algorithm-trie/