Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。
Trie树可以利用字符串的公共前缀来节约存储空间。
参考：http://hi.baidu.com/zealot886/item/08ef4cbe791c404ebb0e124f
下面是我自己实现的trie树
|
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
|
#include <iostream>#include <string>#include <set>#include <fstream>using
namespace std;
#define MAXSIZE 26class
TrieNode
{public:
int
freq;
char
nodechar;
TrieNode *children[MAXSIZE];
set<int> hashset;
TrieNode()
{
for(int
i=0; i<MAXSIZE; i++)
{
children[i] = NULL;
}
freq = 0;
}
};class
TrieTree
{public:
void
AddTrieNode(TrieNode *root, string word, int
id);
void
DeleteTrieNode(TrieNode *root, string word);
int
wordCount( TrieNode *root, string word);
set<int> SearchTrie( TrieNode *root,string word);
TrieTree()
{
p_root = new
TrieNode();
}
public:
TrieNode *p_root;
};
void
TrieTree::AddTrieNode(TrieNode *root, string word, int
id)
{ //cout<<word<<endl;
if(word.length() == 0)
{return
;}
int
k = tolower(word.at(0)) - ‘a‘;
if(root->children[k] == NULL)
{
root->children[k] = new
TrieNode();
root->children[k]->nodechar = word.at(0);
}
root->children[k]->freq++;
root->children[k]->hashset.insert(id);
string nextword = word.substr(1, string::npos);
AddTrieNode(root->children[k], nextword, id);
}void
TrieTree::DeleteTrieNode(TrieNode *root, string word)
{ if(word.length() == 0)
{return
;}
int
k = word.at(0) - ‘a‘;
if(root->children[k] == NULL)
{return
;}
if
(root->children[k]->freq > 0)
{
root->children[k]->freq--;
}
string nextword = word.substr(1, string::npos);
DeleteTrieNode(root->children[k], nextword);
}int
TrieTree::wordCount(TrieNode *root, string word)
{ if(root == NULL)
{return
0;}
int
num = 0;
int
k = word.at(0) - ‘a‘;
string nextword = word.substr(1, string::npos);
if(nextword.length() == 0)
{
num = root->children[k]->freq;
}
else
{
if(root->children[k] != NULL)
{
num = wordCount(root->children[k], nextword);
}
}
return
num;
}set<int> TrieTree::SearchTrie( TrieNode *root, string word)
{ set<int> rset;
if(root == NULL || word.length() == 0)
{
cout<<"str is null"<<endl;
return
rset;
}
int
k = word.at(0) - ‘a‘;
string nextword = word.substr(1, string::npos);
if(root->children[k] == NULL)
{
return
rset;
}
if(nextword.length() == 0)
{
return
root->children[k]->hashset;
}
if
(root->children[k] != NULL)
{
rset = SearchTrie(root->children[k], nextword);
}
return
rset;
} |