最近在刷题的时候遇到了字典树，字典树又称单词查找树。顾名思义，主要应用于字符串存储和检索，可以便捷的使用公共前缀实现字符串快速检，所以经常被搜索引擎系统用于文本词频统计。其主要思想还是空间换时间。时间复杂度等于O(树高)。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
性质：
- 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
- 每个节点的所有子节点包含的字符都不相同。
搜索过程：
- 从根结点开始一次搜索。
- 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索。
- 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
- 迭代过程…
- 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。
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
| //首先假设节点上的字符为a-z
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;//节点的值
TrieNode() {
num = 1;
son = new TrieNode[SIZE];
isEnd = 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<len; i++) {
int pos=letters[i]-'a';
if(node.son[pos]==null) {
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<len; 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 "";
}
// 遍历经过此节点的单词.
public void preTraverse(TrieNode node, String prefix) {
if (!node.isEnd) {
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<len; 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;
}
}
|