TrieTree

学习链接：https://blog.csdn.net/lisonglisonglisong/article/details/45584721

前缀树解决字符串前缀匹配问题，查找单词是否存在，统计以如“abc”开始的字符串的个数，实现词频统计等。

package class_07;import java.util.HashMap;public class Code_01_TrieTree {public static class TrieNode {
public int path; // 记录有多少个字符经过
public int end; // 记录有多少个字符串以此节点结尾
public TrieNode[] nexts; // 路
//public HashMap<String, TrieNode> nexts; 也可以用HashMap来存储下一个节点
public TrieNode() {
path = 0;
end = 0;
nexts = new TrieNode[26];
}
}public static class Trie {
private TrieNode root;public Trie() {
root = new TrieNode();
}public void insert(String word) {
if (word == null) {
return;
}
char[] chs = word.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) { // 如果没有出现该字符对应的节点，创建
node.nexts[index] = new TrieNode();
}
node = node.nexts[index];
node.path++; // 路径加一
}
node.end++; // 结尾的时候尾节点加一
}public void delete(String word) { //与 insert思路刚好相反
if (search(word) != 0) {
char[] chs = word.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (--node.nexts[index].path == 0) {
node.nexts[index] = null;
return;
}
node = node.nexts[index];
}
node.end--;
}
}public int search(String word) {
if (word == null) {
return 0;
}
char[] chs = word.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
return 0;
}
node = node.nexts[index];
}
return node.end;
}public int prefixNumber(String pre) { // 计算以pre为前缀的字符串个数
if (pre == null) {
return 0;
}
char[] chs = pre.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
return 0;
}
node = node.nexts[index];
}
return node.path;
}
}public static void main(String[] args) {
Trie trie = new Trie();
System.out.println(trie.search("zuo"));
trie.insert("zuo");
System.out.println(trie.search("zuo"));
trie.delete("zuo");
System.out.println(trie.search("zuo"));
trie.insert("zuo");
trie.insert("zuo");
trie.delete("zuo");
System.out.println(trie.search("zuo"));
trie.delete("zuo");
System.out.println(trie.search("zuo"));
trie.insert("zuoa");
trie.insert("zuoac");
trie.insert("zuoab");
trie.insert("zuoad");
trie.delete("zuoa");
System.out.println(trie.search("zuoa"));
System.out.println(trie.prefixNumber("zuo"));}}