代码实现
public class Trie {
static class TrieNode{
char ch;//字符
boolean isEndOfWord;//是否为完整词项
//子节点映射
Map<Character, TrieNode> children;
public TrieNode(char ch) {
this.ch = ch;
this.isEndOfWord=false;
this.children=new HashMap<>();
}
}
private final TrieNode root;
public Trie() {
this.root = new TrieNode('\0');//用'\0'代表根节点
}
//1.插入节点
public void insert(String word){
//从根节点开始插入
TrieNode current=root;
//遍历待查询字符串每个字符
for (char ch:word.toCharArray()){
/**
* 这句代码 current.children.computeIfAbsent(ch, TrieNode::new) 的作用是
*1.在当前节点 current 的子节点映射 children 中查找键为 ch 的条目。
* 2.如果找到了，返回与 ch 关联的子节点。
* 3.如果没找到，使用 TrieNode 构造函数（通过 TrieNode::new 方法引用）创建一个新的 TrieNode 实例，
* 其中字符属性 ch 设置为传递给 computeIfAbsent 的 ch 参数，并将这个新创建的节点作为新值添加到映射中（键为 ch），
* 然后返回这个新创建的节点。
*/
current=current.children.computeIfAbsent(ch,TrieNode::new);
}
//标记当前节点为词项的结束节点
current.isEndOfWord=true;
}
//2.查询字符串是否存在于前缀树中
public boolean search(String word){
//从根节点开始
TrieNode current = root;
//遍历每个字符
for (char ch:word.toCharArray()){
//获取与当前节点对应的子节点,若不存在返回null
TrieNode node = current.children.get(ch);
if (node==null){
return false;
}
current=node;
}
return current.isEndOfWord;
}
//3.删除字符串
public boolean delete(TrieNode currentNode,String word,int index){
//1.若处理完所有字符串
if (index==word.length()){
//若不是则说明字符串不在树中,返回false
if (!currentNode.isEndOfWord){
return false;
}
//将当前节点的词项结束标点设置为false
currentNode.isEndOfWord=false;
//检查当前节点是否还有其他节点
return currentNode.children.isEmpty();
}
//2.若还有字符串没有处理完
//获取待删除字符串的当前节点
char ch = word.charAt(index);
//2.1获取当前节点的子节点,若该节点不存在,返回null
TrieNode node = currentNode.children.get(ch);
if (node==null){
return false;
}
//2.2若找到子节点,递归删除
boolean shouldDeleteCurrentNode = delete(node, word, index + 1);
//2.3如果递归删除子节点后返回true,说明子节点没有了其他节点,该子节点已无用可以删除
if (shouldDeleteCurrentNode){
currentNode.children.remove(ch);
//若当前节点无其他子节点,就删除该节点
return currentNode.children.isEmpty();
}
//2.4若此节点无需删除,返回false
return false;
}
}