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;} |
原文：http://www.cnblogs.com/laon/p/3566194.html