Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较。

1
#ifndef TRIE_H
2
#define TRIE_H
3
4
typedef struct word_trie_t word_trie_t;
5
typedef enum bool bool;
6
7
enum bool
8
{
9
    false = 0,
10
    true = 1,
11
};
12
13
struct word_trie_t
14
{
15
    bool (*insert)(word_trie_t *this, char *str);
16
    bool (*find_word)(word_trie_t *this, char *str);
17
    int (*find_prefix)(word_trie_t *this, char *str);
18
    bool (*delete)(word_trie_t *this, char *str);
19
    void (*destroy)(word_trie_t *this);
20
};
21
22
word_trie_t *word_trie_create();
23
#endif
1
#include "trie.h"
2
#include<stdio.h>
3
#include<string.h>
4
#include<malloc.h>
5
6
#define TRIE_NODE_MAX 26
7
8
typedef struct trie_node_t trie_node_t;
9
10
struct trie_node_t
11
{
12
    int count;      //用来计算前缀数
13
    bool is_str;    //用来标识到此的字符串
14
    trie_node_t *word[TRIE_NODE_MAX];
15
};
16
17
trie_node_t* trie_node_create()
18
{
19
    trie_node_t* node=(trie_node_t*)malloc(sizeof(trie_node_t));
20
    memset(node, 0, sizeof(trie_node_t));       //node->is_str = 0;
21
    return node;
22
}
23
24
void trie_node_destroy(trie_node_t *node)
25
{
26
    free(node);
27
}
28
29
typedef struct private_word_trie_t private_word_trie_t;
30
struct private_word_trie_t
31
{
32
    word_trie_t public;
33
    trie_node_t *root;
34
};
35
36
bool insert(private_word_trie_t *this, char *str)
37
{
38
    printf("comming insert function...\n");
39
    trie_node_t *current=this->root;
40
    int word_pos;
41
    while(*str)
42
    {
43
        word_pos = *str-'a';
44
        if(current->word[word_pos] == NULL)
45
        {
46
            current->word[word_pos]=trie_node_create();
47
        }
48
        current=current->word[word_pos];
49
        
50
        str++;
51
    }
52
    current->count++;
53
    current->is_str = true;
54
    return true;
55
}
56
57
bool find_word(private_word_trie_t *this, char *str)
58
{
59
    printf("comming find_word function...\n");
60
    trie_node_t *current = this->root;
61
    int word_pos;
62
    while(*str)
63
    {
64
        word_pos = *str-'a';
65
        if((current = current->word[word_pos]) == NULL)
66
        {
67
            return false;
68
        }
69
        str++;
70
    }
71
    return current->is_str;
72
}
73
74
int find_prefix(private_word_trie_t *this, char *str)
75
{
76
    trie_node_t *current = this->root;
77
    int word_pos;
78
    while(*str)
79
    {
80
        word_pos=*str-'a';
81
        if((current = current->word[word_pos]) == NULL)
82
        {
83
            return 0;
84
        }
85
        str++;
86
    }
87
    return current->count;
88
}
89
90
bool delete(private_word_trie_t *this, char *str)
91
{
92
    trie_node_t *current = this->root;
93
    int word_pos;
94
    trie_node_t *del = NULL;
95
    if(find_word(this,str))
96
    {
97
        while(*str)
98
        {
99
            word_pos = *str-'a';
100
            if(((current->word[word_pos])->count--) == 0)
101
            {
102
                del=current->word[word_pos];
103
                current->word[word_pos] = NULL;
104
                str++;
105
                break;
106
            }
107
            str++;
108
        }
109
110
        if(del!=NULL)
111
        {
112
            while(*str)
113
            {
114
                word_pos = *str-'a';
115
                current = del;
116
                del=current->word[word_pos];
117
                trie_node_destroy(current);
118
                str++;
119
            }
120
            trie_node_destroy(del);
121
        }
122
        return true;
123
    }
124
    else
125
    {
126
        return false;
127
    }
128
}
129
130
void trie_destroy(trie_node_t *node)
131
{
132
    int i;
133
    for(i=0; i<TRIE_NODE_MAX; i++)
134
    {
135
        if(node->word[i]!=NULL)
136
        {
137
            trie_destroy(node->word[i]);
138
        }
139
    }
140
    trie_node_destroy(node);
141
}
142
143
void destroy(private_word_trie_t *this)
144
{
145
    trie_destroy(this->root);
146
    free(this);
147
}
148
149
word_trie_t *word_trie_create()
150
{
151
    private_word_trie_t *this = (private_word_trie_t*)malloc(sizeof(private_word_trie_t));
152
    this->public.insert = (bool (*)(word_trie_t *, char *))insert;
153
    this->public.find_word = (bool (*)(word_trie_t *, char *))find_word;
154
    this->public.find_prefix = (int (*)(word_trie_t *, char *))find_prefix;
155
    this->public.delete = (bool (*)(word_trie_t *, char *))delete;
156
    this->public.destroy=(void (*)(word_trie_t *))destroy;
157
    this->root = trie_node_create();
158
    return &this->public;
159
}