字典樹

多用於單詞查找的樹形結構圖

又稱單詞查找樹，Trie樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用於統計，排序和保存大量的字元串（但不僅限於字元串），所以經常被搜索引擎系統用於文本詞頻統計。它的優點是：利用字元串的公共前綴來減少查詢時間，最大限度地減少無謂的字元串比較，查詢效率比哈希樹高。

目錄
1性質 2實現方法 3應用 串的快速檢索
串排序 最長公共前綴 4代碼實現

性質

它有3個基本性質：
根節點不包含字元，除根節點外每一個節點都只包含一個字元；從根節點到某一節點，路徑上經過的字元連接起來，為該節點對應的字元串；每個節點的所有子節點包含的字元都不相同。

實現方法

搜索字典項目的方法為：
(1) 從根結點開始一次搜索；
(2) 取得要查找關鍵詞的第一個字母，並根據該字母選擇對應的子樹並轉到該子樹繼續進行檢索；
(3) 在相應的子樹上，取得要查找關鍵詞的第二個字母，並進一步選擇對應的子樹進行檢索。
(4) 迭代過程……
(5) 在某個結點處，關鍵詞的所有字母已被取出，則讀取附在該結點上的信息，即完成查找。其他操作類似處理

應用

串的快速檢索

給出N個單片語成的熟詞表，以及一篇全用小寫英文書寫的文章，請你按最早出現的順序寫出所有不在熟詞表中的生詞。在這道題中，我們可以用數組枚舉，用哈希，用字典樹，先把熟詞建一棵樹，然後讀入文章進行比較，這種方法效率是比較高的。

串排序

給定N個互不相同的僅由一個單詞構成的英文名，讓你將他們按字典序從小到大輸出，用字典樹進行排序，採用數組的方式創建字典樹，這棵樹的每個結點的所有兒子很顯然地按照其字母大小排序。對這棵樹進行先序遍歷即可。

最長公共前綴

對所有串建立字典樹，對於兩個串的最長公共前綴的長度即他們所在的結點的公共祖先個數，於是，問題就轉化為當時公共祖先問題。

代碼實現

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Trie:
# 初始化
def __init__(self):
self.root = {}
self.end = "#"
 
# 添加單詞
def add(self, word: str):
node = self.root
for char in word:
node = node.setdefault(char, {})
node[self.end] = None
 
# 搜索單詞是否存在
def search(self, word):
node = self.root
for char in word:
if char not in node:
return False
node = node[char]
return self.end in node
Java
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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
packagecom.suning.search.test.tree.trie;
 
public class Trie
{
private int SIZE=26;
private TrieNode root;//字典樹的根
 
Trie() //初始化字典樹
{
root=new TrieNode();
}
 
private class TrieNode //字典樹節點
{
private int num;//有多少單詞通過這個節點，即由根至該節點組成的字元串模式出現的次數
private TrieNode[] son;//所有的兒子節點
private boolean isEnd;//是不是最後一個節點
private char val;//節點的值
private boolean haveSon;
 
TrieNode()
{
num=1;
son=new TrieNode[SIZE];
isEnd=false;
haveSon=false;
}
}
 
//建立字典樹
public void insert(String str) //在字典樹中插入一個單詞
{
if(str==null||str.length()==0)
{
return;
}
TrieNode node=root;
char[]letters=str.toCharArray();
for(int i=0,len=str.length(); i
{
int pos=letters[i]-'a';
if(node.son[pos]==null)
{
node.haveSon = true;
node.son[pos]=newTrieNode();
node.son[pos].val=letters[i];
}
else
{
node.son[pos].num++;
}
node=node.son[pos];
}
node.isEnd=true;
}
 
//計算單詞前綴的數量
public int countPrefix(Stringprefix)
{
if(prefix==null||prefix.length()==0)
{
return-1;
}
TrieNode node=root;
char[]letters=prefix.toCharArray();
for(inti=0,len=prefix.length(); i
{
int pos=letters[i]-'a';
if(node.son[pos]==null)
{
return 0;
}
else
{
node=node.son[pos];
}
}
return node.num;
}
//列印指定前綴的單詞
public String hasPrefix(String prefix)
{
if (prefix == null || prefix.length() == 0)
{
return null;
}
TrieNode node = root;
char[] letters = prefix.toCharArray();
for (int i = 0, len = prefix.length(); i < len; i++)
{
int pos = letters[i] - 'a';
if (node.son[pos] == null)
{
return null;
}
else
{
node = node.son[pos];
}
}
preTraverse(node, prefix);
return null;
}
// 遍歷經過此節點的單詞.
public void preTraverse(TrieNode node, String prefix)
{
if (node.haveSon)
{
for (TrieNode child : node.son)
{
if (child!=null)
{
preTraverse(child, prefix+child.val);
}
}
return;
}
System.out.println(prefix);
}
 
 
//在字典樹中查找一個完全匹配的單詞.
public boolean has(Stringstr)
{
if(str==null||str.length()==0)
{
return false;
}
TrieNode node=root;
char[]letters=str.toCharArray();
for(inti=0,len=str.length(); i
{
intpos=letters[i]-'a';
if(node.son[pos]!=null)
{
node=node.son[pos];
}
else
{
return false;
}
}
return node.isEnd;
}
 
//前序遍歷字典樹.
public void preTraverse(TrieNodenode)
{
if(node!=null)
{
System.out.print(node.val+"-");
for(TrieNodechild:node.son)
{
preTraverse(child);
}
}
}
 
public TrieNode getRoot()
{
return this.root;
}
 
public static void main(String[]args)
{
Trietree=newTrie();
String[]strs= {"banana","band","bee","absolute","acm",};
String[]prefix= {"ba","b","band","abc",};
for(Stringstr:strs)
{
tree.insert(str);
}
System.out.println(tree.has("abc"));
tree.preTraverse(tree.getRoot());
System.out.println();
//tree.printAllWords();
for(Stringpre:prefix)
{
int num=tree.countPrefix(pre);
System.out.println(pre+""+num);
}
}
}
C語言
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
#define MAX 26//字符集大小
typedef struct TrieNode
{
int nCount;//記錄該字元出現次數
struct TrieNode* next[MAX];
}TrieNode;
 
TrieNode Memory[1000000];
int allocp=0;
 
void InitTrieRoot(TrieNode* *pRoot)
{
*pRoot=NULL;
}
 
TrieNode* CreateTrieNode()
{
int i;
TrieNode *p;
p=&Memory[allocp++];
p->nCount=1;
for(i=0;i
{
p->next[i]=NULL;
}
return p;
}
 
void InsertTrie(TrieNode* *pRoot,char *s)
{
int i,k;
TrieNode*p;
if(!(p=*pRoot))
{
p=*pRoot=CreateTrieNode();
}
i=0;
while(s[i])
{
k=s[i++]-'a';//確定branch
if(!p->next[k])
p->next[k]=CreateTrieNode();
else
p->next[k]->nCount++;
p=p->next[k];
}
}
 
//查找
int SearchTrie(TrieNode* *pRoot,char *s)
{
TrieNode *p;
int i,k;
if(!(p=*pRoot))
{
return0;
}
i=0;
while(s[i])
{
k=s[i++]-'a';
if(p->next[k]==NULL) return 0;
p=p->next[k];
}
return p->nCount;
}
C++
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
161
162
#include
#include
#include <conio.h>
using namespace std;
namespace trie
{
template size_t CHILD_MAX>
struct nod
{
T reserved;
nod *child[CHILD_MAX];
nod()
{
memset(this, 0, sizeof *this);
}
~nod()
{
for (unsigned i = 0; i < CHILD_MAX; i++)
delete child[i];
}
void Traversal(char *str, unsigned index)
{
unsigned i;
for (i = 0; i < index; i++)
cout << str[i];
cout << '\t' << reserved << endl;
for (i = 0; i < CHILD_MAX; i++)
{
if (child[i])
{
str[index] = i;
child[i]->Traversal(str, index + 1);
}
}
return;
}
};
 
template
class trie
{
private:
nod root;
 
public:
nod *AddStr(char *str);
nod *FindStr(char *str);
bool DeleteStr(char *str);
void Traversal()
{
char str[100];
root.Traversal(str, 0);
}
};
 
template
nod * trie::AddStr(char *str)
{
nod *now = &root;
do
{
if (now->child[*str] == NULL)
now->child[*str] = new nod;
now = now->child[*str];
}
while (*(++str) != '\0');
return now;
}
 
template
nod *trie::FindStr(char *str)
{
nod *now = &root;
do
{
if (now->child[*str] == NULL)
return NULL;
now = now->child[*str];
}
while (*(++str) != '\0');
return now;
}
 
template
bool trie::DeleteStr(char *str)
{
nod **nods = new nod *[strlen(str)];
int snods = 1;
nod *now = &root;
nods[0] = &root;
do
{
if (now->child[*str] == NULL)
return false;
nods[snods++] = now = now->child[*str];
}
while (*(++str) != '\0');
snods--;
while (snods > 0)
{
for (unsigned i = 0; i < CHILD_MAX; i++)
if (nods[snods]->child[i] != NULL)
return true;
delete nods[snods];
nods[--snods]->child[*(--str)] = NULL;
}
return true;
}
} // namespace trie
int main()
{
//TestProgram
trie::trie tree;
while (1)
{
cout << "1 for add a string" << endl;
cout << "2 for find a string" << endl;
cout << "3 for delete a string" << endl;
cout << "4 for traversal" << endl;
cout << "5 for exit" << endl;
char str[100];
switch (getch())
{
case '1':
cout << "Input a string: ";
cin.getline(str, 100);
cout << "This string has existed for " << tree.AddStr(str)->reserved++ << " times." << endl;
break;
case '2':
cout << "Input a string: ";
cin.getline(str, 100);
trie::nod *find;
find = tree.FindStr(str);
if (!find)
cout << "No found." << endl;
else
cout << "This string has existed for " << find->reserved << " times." << endl;
break;
case '3':
cout << "Input a string: ";
cin.getline(str, 100);
cout << "The action is " << (tree.DeleteStr(str) ? "Successful." : "Unsuccessful.") << endl;
break;
case '4':
cout << "Traversal the tree: " << endl;
tree.Traversal();
break;
case '5':
cout << "Exit." << endl;
return 0;
}
}
return 0;
}

基本信息

中文名
字典樹
外文名
trie tree
別名
單詞查找樹
類型
樹形結構
基本操作
查找、插入和刪除