本文内容主要来源：https://www.cnblogs.com/konrad/p/7748508.html
- 定义节点类TrieNode
public class TrieNode {
private List<TrieNode> children; //子节点
private char data; //节点字符
private int freq; //频率
boolean isEnd; //从根节点到该节点是否是一个词
public TrieNode(char data){
this.children = new LinkedList<>();
this.freq = 0;
this.isEnd = false;
this.data = data;
}
public TrieNode childNode(char c){
if(null != children){
for(TrieNode child : children){
if(child.getData() == c){
return child;
}
}
}
return null;
}
public List<TrieNode> getChildren() {
return children;
}
public void setChildren(List<TrieNode> children) {
this.children = children;
}
public char getData() {
return data;
}
public void setData(char data) {
this.data = data;
}
public int getFreq() {
return freq;
}
public void setFreq(int freq) {
this.freq = freq;
}
public void addFreq(int step){
this.freq += step;
}
public void subFreq(int step){
this.freq -= step;
}
public boolean isEnd() {
return isEnd;
}
public void setEnd(boolean end) {
isEnd = end;
}
}
- 定义Trie树类TrieTree
public class TrieTree {
private TrieNode root;
public TrieTree() {
this.root = new TrieNode(' ');
}
//查找是否存在
public boolean search(String word) {...}
//查找返回节点
public TrieNode searchNode(String word) {...}
//插入
public void insert(String word) {...}
//移除
public void remove(String word) {...}
//获取词频
public int getFreq(String word) {...}
}
- 插入节点
public void insert(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
TrieNode child = current.childNode(word.charAt(i));
if (null != child)
current = child;
else {
current.getChildren().add(new Trde(word.charAt(i)));
current = current.childNode(word.charAt(i));
}
current.addFreq(1);
}
current.setEnd(true);
}
4.查找节点
//查找是否存在
public boolean search(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
if (null == current.childNode(word.charAt(i)))
return false;
else
current = current.childNode(word.charAt(i));
}
if (current.isEnd())
return true;
else
return false;
}
//查找返回节点
public TrieNode searchNode(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
if (null == current.childNode(word.charAt(i)))
return null;
else
current = current.childNode(word.charAt(i));
}
if (current.isEnd())
return current;
else
return null;
}
- 删除节点
public void remove(String word) {
if (!search(word))
return;
TrieNode current = root;
for (char c : word.toCharArray()) {
TrieNode child = current.childNode(c);
if (child.getFreq() == 1) {
current.getChildren().remove(child);
return;
}else{
child.subFreq(1);
current = child;
}
}
current.setEnd(false);
}
- 获取某个词的频率
//获取词频
public int getFreq(String word) {
TrieNode trieNode = searchNode(word);
if(null != trieNode){
return trieNode.getFreq();
}else{
return 0;
}
}
这只是Trie树的实现方法之一，也可以使用其他不同方式来实现。
上一篇：Trie 树（一）：简介
下一篇：java 正则表达式中断言的使用
