数据结构
字典树是一种特殊的多叉树，它虽然是树形结构但是设计出来却是为了方便查找存储的字符串类型的。 字典树的数据结构跟一般的多叉树不同，它的子节点的指针是存放在26个字母表长度的数组中的. TrieNode中保存了下一个字符可能出现的所有字符的链接，我们可以通过当前节点预知所有子节点的值。
struct TrieNode {
bool isEnd; // 该结点是否是一个串的结束
TrieNode* next[26]; //字母映射表
};
例如直接遍历next数组，可以知道下一个字符哪一个链接了子串哪一个没存放字符。
for(int i=0;i<26;i++){
char c = a + 'i';
if (next[i] == null){
// 未存储字符
}else {
// 已存储字符
}
}
如果字典树中存储了三个单词”sea”, “sells”, “she”,那么字典树的树形结构会是这样： ![[Pasted image 20240921074557.png]]
字典树的构建
class Trie {
// 构建节点
class TrieNode{
// 节点类型
private boolean isEnd;
// 当前class类型的数组对象
TrieNode[] next;
// 初始化当前类
public TrieNode(){
isEnd = false;
next = new TrieNode[26];
}
}
// 定义根节点
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
// 从头节点开始遍历树，构建当前字符链表
TrieNode node = root;
// 从当前字符开始查询
for (int i=0;i<word.length();i++){
char c = word.charAt(i);
int posi = c-'a';
// 直接引用next[]属性
// 一直查找，如果当前字符已经存放过就查找下一个节点
// 如果当前字符未存放过就填充当下位置当前数组的指针
if (node.next[posi]==null){
// 当前字符未存入过,当前位置存放指向下一个字符的指针
// 此时下层节点同样未存放下一个字符
node.next[posi] = new TrieNode();
}
// 节点指针下移,此时指向一个新的空数据结构
node = node.next[posi];
}
// 标记该位置是一个字符结尾
node.isEnd = true;
}
// 检查该单词是否存在
public boolean search(String word) {
TrieNode node = root;
for (int i=0;i<word.length();i++){
int p = word.charAt(i)-'a';
if (node.next[p]==null){
return false;
}
node = node.next[p];
}
return node.isEnd;
}
public boolean startsWith(String prefix) {
TrieNode node = root;
for (int i=0;i<prefix.length();i++){
int p = prefix.charAt(i)-'a';
if (node.next[p]==null){
return false;
}
node = node.next[p];
}
return true;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
