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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#ifndef TRIE_H
#define TRIE_H

typedef struct word_trie_t word_trie_t;
typedef enum bool bool;

enum bool
{
    false = 0,
    true = 1,
};

struct word_trie_t
{
    bool (*insert)(word_trie_t *this, char *str);
    bool (*find_word)(word_trie_t *this, char *str);
    int (*find_prefix)(word_trie_t *this, char *str);
    bool (*delete)(word_trie_t *this, char *str);
    void (*destroy)(word_trie_t *this);
};

word_trie_t *word_trie_create();
#endif
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include "trie.h"
#include<stdio.h>
#include<string.h>
#include<malloc.h>

#define TRIE_NODE_MAX 26

typedef struct trie_node_t trie_node_t;

struct trie_node_t
{
    int count;      //用来计算前缀数
    bool is_str;    //用来标识到此的字符串
    trie_node_t *word[TRIE_NODE_MAX];
};

trie_node_t* trie_node_create()
{
    trie_node_t* node=(trie_node_t*)malloc(sizeof(trie_node_t));
    memset(node, 0, sizeof(trie_node_t));       //node->is_str = 0;
    return node;
}

void trie_node_destroy(trie_node_t *node)
{
    free(node);
}

typedef struct private_word_trie_t private_word_trie_t;
struct private_word_trie_t
{
    word_trie_t public;
    trie_node_t *root;
};

bool insert(private_word_trie_t *this, char *str)
{
    printf("comming insert function...\n");
    trie_node_t *current=this->root;
    int word_pos;
    while(*str)
    {
        word_pos = *str-'a';
        if(current->word[word_pos] == NULL)
        {
            current->word[word_pos]=trie_node_create();
        }
        current=current->word[word_pos];
        
        str++;
    }
    current->count++;
    current->is_str = true;
    return true;
}

bool find_word(private_word_trie_t *this, char *str)
{
    printf("comming find_word function...\n");
    trie_node_t *current = this->root;
    int word_pos;
    while(*str)
    {
        word_pos = *str-'a';
        if((current = current->word[word_pos]) == NULL)
        {
            return false;
        }
        str++;
    }
    return current->is_str;
}

int find_prefix(private_word_trie_t *this, char *str)
{
    trie_node_t *current = this->root;
    int word_pos;
    while(*str)
    {
        word_pos=*str-'a';
        if((current = current->word[word_pos]) == NULL)
        {
            return 0;
        }
        str++;
    }
    return current->count;
}

bool delete(private_word_trie_t *this, char *str)
{
    trie_node_t *current = this->root;
    int word_pos;
    trie_node_t *del = NULL;
    if(find_word(this,str))
    {
        while(*str)
        {
            word_pos = *str-'a';
            if(((current->word[word_pos])->count--) == 0)
            {
                del=current->word[word_pos];
                current->word[word_pos] = NULL;
                str++;
                break;
            }
            str++;
        }

        if(del!=NULL)
        {
            while(*str)
            {
                word_pos = *str-'a';
                current = del;
                del=current->word[word_pos];
                trie_node_destroy(current);
                str++;
            }
            trie_node_destroy(del);
        }
        return true;
    }
    else
    {
        return false;
    }
}

void trie_destroy(trie_node_t *node)
{
    int i;
    for(i=0; i<TRIE_NODE_MAX; i++)
    {
        if(node->word[i]!=NULL)
        {
            trie_destroy(node->word[i]);
        }
    }
    trie_node_destroy(node);
}

void destroy(private_word_trie_t *this)
{
    trie_destroy(this->root);
    free(this);
}

word_trie_t *word_trie_create()
{
    private_word_trie_t *this = (private_word_trie_t*)malloc(sizeof(private_word_trie_t));
    this->public.insert = (bool (*)(word_trie_t *, char *))insert;
    this->public.find_word = (bool (*)(word_trie_t *, char *))find_word;
    this->public.find_prefix = (int (*)(word_trie_t *, char *))find_prefix;
    this->public.delete = (bool (*)(word_trie_t *, char *))delete;
    this->public.destroy=(void (*)(word_trie_t *))destroy;
    this->root = trie_node_create();
    return &this->public;
}