什么是前缀树，有什么作用？
2026/1/14...大约 3 分钟Java八股文
注意
内容来源网络，仅供学习使用。
不要相信文档中的链接、联系方式等！！！
什么是前缀树，有什么作用？
典型回答
前缀树（Trie，又称字典树或键树）是一种树形结构，它是一种用于快速检索字符串集合中字符串的高效数据结构。前缀树的每个节点代表一个字符串（或字符串的一部分），从根节点到某一节点的路径上经过的字符连接起来，就是该节点对应的字符串。
前缀树的特点：
- 根节点不包含字符，除根节点外的每个节点都只包含一个字符。
- 从根节点到某一节点的路径上经过的字符连接起来，为该节点对应的字符串。
- 每个节点的所有子节点包含的字符都不相同。
举个例子：有以下字符串：
abc,bac,bbc,ca，
通过字典树形成的结构如下所示：
从上图我们可以看出，通过字典树，在查询的时候，原来的时间复杂度是O(n*m)，优化后的时间复杂度就会变成O(m)。同时，如果有很多字符串，字典树还可以大大减少存储的空间。
字典树的java实现如下所示：
class Trie {
private Trie[] children;
private boolean isWord;
public Trie() {
this.isWord = false;
this.children = new Trie[26];
}
public void insert(String word) {
Trie next = this;
for(char c : word.toCharArray()) {
if(next.children[c - 'a'] == null) {
next.children[c - 'a'] = new Trie();
}
next = next.children[c - 'a'];
}
next.isWord = true;
}
public boolean search(String word) {
Trie next = this;
for(char c : word.toCharArray()) {
if(next.children[c - 'a'] == null) {
return false;
}
next = next.children[c - 'a'];
}
return next.isWord;
}
public boolean startsWith(String prefix) {
Trie next = this;
for(char c : prefix.toCharArray()) {
if(next.children[c - 'a'] == null) {
return false;
}
next = next.children[c - 'a'];
}
return true;
}
}