字典树（Trie）详解 + Java 代码实现

目录一、字典树核心概念1. 结构特点2. 核心应用场景3. 时间复杂度二、字典树结构设计三、完整 Java 代码实现四、代码逐段讲解1. 节点类 TrieNode2. 插入方法 insert3. 查询单词 search4. 查询前缀 startsWith五、字典树优点 vs 缺点优点缺点六、扩展支持大小写 / 特殊字符扩展版 Java 代码总结字典树Trie也叫前缀树是一种多叉树专门用于高效存储和查找字符串集合的数据结构。它的核心优势利用字符串的公共前缀减少存储空间极大提升查询效率。一、字典树核心概念1. 结构特点根节点不存储字符其余每个节点存储一个字符。从根节点到某一个节点路径上的字符连接起来就是对应的字符串。拥有公共前缀的字符串会共享树的节点。节点标记用一个布尔值标记当前节点是否是字符串的结尾。2. 核心应用场景字符串前缀匹配搜索框自动补全单词检索字典、拼写检查IP 路由最长前缀匹配字符串去重3. 时间复杂度插入O(L)L 是字符串长度查询O(L)前缀查询O(L)远优于哈希表无哈希冲突和暴力匹配。二、字典树结构设计我们用节点类 主类实现TrieNode字典树节点children[]子节点数组26 个字母对应 a-zisEnd标记是否是单词结尾Trie字典树主类根节点插入方法insert查询完整单词方法search查询前缀方法startsWith三、完整 Java 代码实现/** * 字典树节点类 */ class TrieNode { // 子节点数组26个小写英文字母 TrieNode[] children; // 标记当前节点是否是一个单词的结尾 boolean isEnd; public TrieNode() { children new TrieNode[26]; isEnd false; } } /** * 字典树前缀树主类 */ public class Trie { // 根节点 private TrieNode root; public Trie() { // 初始化根节点 root new TrieNode(); } /** * 向字典树插入一个单词 * param word 待插入的单词 */ public void insert(String word) { // 从根节点开始遍历 TrieNode cur root; for (char c : word.toCharArray()) { // 计算字符对应的索引 0-25 int index c - a; // 如果子节点不存在创建新节点 if (cur.children[index] null) { cur.children[index] new TrieNode(); } // 移动到子节点 cur cur.children[index]; } // 单词遍历结束标记结尾 cur.isEnd true; } /** * 查询字典树中是否存在这个单词 * param word 待查询单词 * return 存在返回true否则false */ public boolean search(String word) { TrieNode cur root; for (char c : word.toCharArray()) { int index c - a; // 某个字符不存在直接返回false if (cur.children[index] null) { return false; } cur cur.children[index]; } // 必须走到单词结尾才算找到 return cur.isEnd; } /** * 查询字典树中是否有以该前缀开头的单词 * param prefix 前缀 * return 存在返回true */ public boolean startsWith(String prefix) { TrieNode cur root; for (char c : prefix.toCharArray()) { int index c - a; if (cur.children[index] null) { return false; } cur cur.children[index]; } // 只要能遍历完前缀就返回true不需要判断是否是单词结尾 return true; } // 测试 public static void main(String[] args) { Trie trie new Trie(); // 插入单词 trie.insert(apple); trie.insert(app); trie.insert(banana); // 查询单词 System.out.println(trie.search(apple)); // true System.out.println(trie.search(app)); // true System.out.println(trie.search(appl)); // false // 查询前缀 System.out.println(trie.startsWith(app)); // true System.out.println(trie.startsWith(ban)); // true System.out.println(trie.startsWith(xyz)); // false } }四、代码逐段讲解1. 节点类TrieNodechildren[26]存储 26 个小写字母的子节点。isEnd标记当前节点是不是单词最后一个字符。2. 插入方法insert从根节点出发。遍历单词的每一个字符。字符对应索引不存在 → 创建新节点。遍历完成后标记isEnd true。3. 查询单词search遍历字符节点不存在直接返回false。遍历结束后必须判断 isEnd确保是完整单词。4. 查询前缀startsWith只需要判断路径是否存在。不需要判断是否是单词结尾。五、字典树优点 vs 缺点优点前缀查询极快。天然去重相同前缀不重复存储。无哈希冲突问题。缺点空间消耗大如果字符串前缀重复少空间成本高。只适合字符串类型不适合数字范围查询。六、扩展支持大小写 / 特殊字符如果需要支持大小写字母、数字可以把数组换成HashMapCharacter, TrieNode。扩展版 Java 代码import java.util.HashMap; class TrieNodeMap { HashMapCharacter, TrieNodeMap children; boolean isEnd; public TrieNodeMap() { children new HashMap(); isEnd false; } } public class TrieMap { private TrieNodeMap root; public TrieMap() { root new TrieNodeMap(); } public void insert(String word) { TrieNodeMap cur root; for (char c : word.toCharArray()) { cur.children.putIfAbsent(c, new TrieNodeMap()); cur cur.children.get(c); } cur.isEnd true; } public boolean search(String word) { TrieNodeMap cur root; for (char c : word.toCharArray()) { if (!cur.children.containsKey(c)) return false; cur cur.children.get(c); } return cur.isEnd; } public boolean startsWith(String prefix) { TrieNodeMap cur root; for (char c : prefix.toCharArray()) { if (!cur.children.containsKey(c)) return false; cur cur.children.get(c); } return true; } }总结字典树 前缀树用于字符串快速查找 前缀匹配。核心结构节点数组 结束标记。三大方法insert、search、startsWith。时间复杂度O(L)空间换时间。标准场景搜索提示、字典、拼写检查、IP 匹配。