前缀树，又称为Trie树，是一种树形数据结构，可用于高效地存储和检索字符串数据集合中的键，常用于自动补完和拼写检查等应用场景。下面对是对前缀树节点的定义：
1
2
3
4
| class WordNetTree {
boolean end;
WordNetTree[] words = new WordNetTree[26];
}
|
其中end代表当前节点是否为结尾；words代表每个节点中的集合，数组长度为26，代表每次创建一个WordNetTree节点时，都会在该节点内部创建一个长度为26的WordNetTree数组。
如果对单词app、apple、apply、ben采用前缀树进行存储，则该前缀树存储的单词可形象的表示为下面形式：
如上图所示，每一个WordNetTree对象中，都包含长度为26的WordNetTree数组，数组中的下标i对应字母a~z，这里以小写字母为例。在存储apple和apply时，可以对相同前缀的字母存储时，复用其节点。同时，通过end值为False或者True，对该字符串进行判断——以root开始，当前节点结尾的字符串是否为完整字符串。
假设root节点为起始节点。那么对字符串插入，则有：
1
2
3
4
5
6
7
8
9
10
11
12
|
public void insert(String word) {
WordNetTree start = root;
for(int i = 0;i < word.length();++i) {
int index = word.charAt(i) - 'a';
if(start.words[index] == null) {
start.words[index] = new WordNetTree();
}
start = start.words[index];
}
start.end = true;
}
|
该函数的主要逻辑是，遍历该字符串中的每个字符，通过该字符定位到WordNetTree中的下标位置（下标位置和字符做一一对应的映射关系）。如果当前位置的对象为null，那么创建新的节点对象，用于标记当前index位置的对象数组，并将指针移动到当前字符位置，用于定位下一个字符位置。当遍历完成整个字符串时，将最后一个位置的end标记为True，表明当前结尾的字符串为完整字符串。
那么对字符串进行搜索时，则有：
1
2
3
4
5
6
7
8
9
10
11
12
|
public boolean search(String word) {
WordNetTree start = root;
for(int i = 0;i < word.length();++i) {
int index = word.charAt(i) - 'a';
if(start.words[index] == null) {
return false;
}
start = start.words[index];
}
return start.end;
}
|
如果，在搜索过程中，对象为null，则表明未存储当前字符串；在遍历完整个字符串时，返回end的值，如果end为False，表明尽管搜索到了当前字符串，但是该字符串只是某一字符串的前缀子串，并非为完整存储的字符串。
那么对字符串进行前缀匹配时，则有：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public boolean startsWith(String prefix) {
WordNetTree start = root;
for(int i = 0;i < prefix.length();++i) {
int index = prefix.charAt(i) - 'a';
if(start.words[index] == null){
return false;
}
start = start.words[index];
}
return true;
}
|
下面给出完整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
| class Trie {
private WordNetTree root;
public Trie() {
root = new WordNetTree();
}
public void insert(String word) {
WordNetTree start = root;
for(int i = 0;i < word.length();++i) {
int index = word.charAt(i) - 'a';
if(start.words[index] == null) {
start.words[index] = new WordNetTree();
}
start = start.words[index];
}
start.end = true;
}
public boolean search(String word) {
WordNetTree start = root;
for(int i = 0;i < word.length();++i) {
int index = word.charAt(i) - 'a';
if(start.words[index] == null) {
return false;
}
start = start.words[index];
}
return start.end;
}
public boolean startsWith(String prefix) {
WordNetTree start = root;
for(int i = 0;i < prefix.length();++i) {
int index = prefix.charAt(i) - 'a';
if(start.words[index] == null){
return false;
}
start = start.words[index];
}
return true;
}
class WordNetTree {
boolean end;
WordNetTree[] words = new WordNetTree[26];
}
}
|
