第 12 课：Trie 树（前缀树）—— 专门处理字符串前缀匹配的神器

这是字符串类问题的终极杀器。当你遇到任何与 "前缀"、"自动补全"、"拼写检查" 相关的问题时，Trie 树几乎永远是最优解。它的核心价值是：利用字符串的公共前缀，将查找时间从 O (n) 降低到 O (L)（L 是字符串的长度）。

一、先想明白：为什么要有 Trie 树？

我们先看看已有的数据结构处理字符串前缀匹配的痛点：

• 哈希表：可以 O (1) 查找一个完整的单词，但无法高效查找所有以某个前缀开头的单词。如果要做前缀匹配，需要遍历所有单词，时间复杂度 O (n)。
• 数组 / 链表：查找和前缀匹配都是 O (n)，效率极低。

举个最常见的例子：你在搜索引擎输入 "数"，它会立刻提示 "数据结构"、"数学"、"数据库"、"数据分析" 等 10 个以 "数" 开头的热门单词。如果用哈希表实现这个功能，需要遍历词库中所有的百万级单词，检查每个单词是否以 "数" 开头，这显然是不可能的。

Trie 树的诞生，就是专门为了解决字符串前缀匹配问题。它把所有单词的公共前缀合并在一起，让前缀匹配的时间只和前缀的长度有关，和词库的大小无关。

二、Trie 树的本质：用树形结构存储公共前缀

✅ 核心思想（刻在脑子里）

Trie 树是一棵多叉树，每个节点代表一个字符。从根节点到某个节点的路径，就是一个完整的字符串。所有以同一个前缀开头的字符串，都共享该前缀对应的路径。

生活化类比

Trie 树就像字典的部首查字法：

• 字典的目录 = Trie 树的根节点
• 部首 = Trie 树的第一层节点
• 部首下面的笔画 = Trie 树的下一层节点
• 你查 "数" 字，先找 "攵" 部，再找对应的笔画，不用翻遍整本字典

举个例子

假设我们有三个单词：apple、app、banana，它们对应的 Trie 树结构是这样的：

plaintext

根节点 / \ a b / \ p a / \ p n / \ \ * l a \ \ e n \ \ * a \ *

• 每个*表示这个节点是一个单词的结尾
• app和apple共享前缀a-p-p，所以它们在 Trie 树中共享前三层节点
• 这就是 Trie 树节省空间和提高效率的原因

三、Trie 树的节点结构

Trie 树的每个节点包含两部分：

1. 子节点：一个数组或哈希表，存储当前节点的所有子节点。因为字符通常是 26 个小写字母，所以最常用的是长度为 26 的数组。
2. 结束标记：一个布尔值，标记这个节点是否是一个单词的结尾。

⚠️ 非常重要的误区：Trie 树的节点本身不存储字符！字符是通过父节点到子节点的边来表示的。

• 根节点到第一个子节点a的边，表示字符a
• 节点a到它的子节点p的边，表示字符p
• 以此类推

Python 节点定义

python

运行

class TrieNode: def __init__(self): self.children = [None] * 26 # 26个小写字母 self.is_end = False # 标记是否是单词结尾

四、Trie 树的三个核心操作

所有操作的时间复杂度都是O(L)，其中 L 是字符串的长度。

1. 插入操作

核心思路

从根节点开始，逐个遍历单词的每个字符：

• 如果当前字符对应的子节点不存在，就创建一个新节点
• 移动到该子节点
• 遍历结束后，将最后一个节点的is_end标记为 True

代码

python

运行

def insert(self, word: str) -> None: node = self.root for char in word: index = ord(char) - ord('a') if not node.children[index]: node.children[index] = TrieNode() node = node.children[index] node.is_end = True

2. 查找操作

核心思路

从根节点开始，逐个遍历单词的每个字符：

• 如果当前字符对应的子节点不存在，说明单词不存在，返回 False
• 移动到该子节点
• 遍历结束后，返回最后一个节点的is_end值（因为一个单词可能是另一个单词的前缀）

代码

python

运行

def search(self, word: str) -> bool: node = self.root for char in word: index = ord(char) - ord('a') if not node.children[index]: return False node = node.children[index] return node.is_end

3. 查找前缀操作

核心思路

和查找操作几乎一模一样，唯一的区别是：遍历结束后，不需要检查is_end，直接返回 True 即可。

代码

python

运行

def startsWith(self, prefix: str) -> bool: node = self.root for char in prefix: index = ord(char) - ord('a') if not node.children[index]: return False node = node.children[index] return True

五、Trie 树的完整实现

python

运行

class Trie: def __init__(self): # 初始化字典树，创建根节点 self.root = TrieNode() def insert(self, word: str) -> None: # 从根节点开始插入单词 node = self.root # 遍历单词中的每个字符 for char in word: # 计算字符在字母表中的索引（假设字符为小写字母） index = ord(char) - ord('a') # 如果当前节点没有该字符的子节点，则创建新节点 if not node.children[index]: node.children[index] = TrieNode() # 移动到子节点 node = node.children[index] # 标记单词结束位置 node.is_end = True def search(self, word: str) -> bool: # 从根节点开始搜索单词 node = self.root # 遍历单词中的每个字符 for char in word: # 计算字符在字母表中的索引 index = ord(char) - ord('a') # 如果当前节点没有该字符的子节点，单词不存在 if not node.children[index]: return False # 移动到子节点 node = node.children[index] # 检查是否为完整单词的结束位置 return node.is_end def startsWith(self, prefix: str) -> bool: # 从根节点开始检查前缀 node = self.root # 遍历前缀中的每个字符 for char in prefix: # 计算字符在字母表中的索引 index = ord(char) - ord('a') # 如果当前节点没有该字符的子节点，前缀不存在 if not node.children[index]: return False # 移动到子节点 node = node.children[index] # 前缀存在 return True

✅ 这就是 Trie 树的完整实现，代码非常简洁，但功能强大。

六、Trie 树的优缺点

优点

1. 前缀匹配极快：时间复杂度 O (L)，和词库大小无关
2. 插入和查找都是 O (L)：和哈希表相当，甚至在短字符串时更快
3. 可以按字典序排序：Trie 树的前序遍历就是字典序

缺点

1. 空间消耗大：每个节点都有一个长度为 26 的数组，即使大部分位置都是空的
2. 只适合处理字符集较小的情况：如果字符集很大（比如中文），空间消耗会非常惊人

七、Trie 树的四大经典应用场景（面试必考）

1. 搜索引擎的自动补全：这是 Trie 树最著名的应用
2. 单词拼写检查：检查输入的单词是否在词库中
3. IP 路由最长前缀匹配：路由器根据 IP 地址的最长前缀匹配路由表
4. 字符串前缀匹配：所有需要查找以某个前缀开头的字符串的场景

八、经典例题（必做）

例题 1：LeetCode 208. 实现 Trie（前缀树）

题目：实现一个 Trie 树，支持insert、search和startsWith操作。这就是我们上面写的完整实现，面试出现频率 100%，必须闭着眼能写出来。

例题 2：LeetCode 211. 添加与搜索单词 - 数据结构设计

题目：请你设计一个数据结构，支持添加新单词和查找字符串是否与任何先前添加的字符串匹配。查找字符串可以包含通配符'.'，'.'可以表示任何一个字母。

核心思路：

• 基础结构还是 Trie 树
• 当遇到通配符'.'时，递归遍历当前节点的所有子节点

代码片段（核心部分）

python

运行

class TrieNode: def __init__(self): # 26个字母的子节点数组，初始为None self.children = [None] * 26 # 标记当前节点是否为单词的结束 self.is_end = False class WordDictionary: def __init__(self): # 初始化字典树，创建根节点 self.root = TrieNode() def addWord(self, word: str) -> None: # 从根节点开始插入单词 node = self.root for char in word: # 计算字符在字母表中的索引（a=0, b=1, ..., z=25） index = ord(char) - ord('a') # 如果当前节点没有该字符的子节点，则创建新节点 if not node.children[index]: node.children[index] = TrieNode() # 移动到子节点 node = node.children[index] # 标记单词结束位置 node.is_end = True def search(self, word: str) -> bool: # 从根节点开始搜索 return self.search_helper(word, self.root, 0) def search_helper(self, word: str, node: TrieNode, index: int) -> bool: # 如果已经遍历完所有字符，检查是否为单词结束 if index == len(word): return node.is_end # 获取当前字符 char = word[index] # 处理通配符'.' if char == '.': # 遍历所有子节点 for child in node.children: # 如果子节点存在且递归搜索成功，返回True if child and self.search_helper(word, child, index + 1): return True # 所有子节点都不匹配，返回False return False else: # 计算字符在字母表中的索引 idx = ord(char) - ord('a') # 如果当前节点没有该字符的子节点，返回False if not node.children[idx]: return False # 递归搜索下一个字符 return self.search_helper(word, node.children[idx], index + 1) # 示例用法 wordDictionary = WordDictionary() wordDictionary.addWord("bad") wordDictionary.addWord("dad") wordDictionary.addWord("mad") # 搜索示例 print(wordDictionary.search("pad")) # 返回 False print(wordDictionary.search("bad")) # 返回 True print(wordDictionary.search(".ad")) # 返回 True print(wordDictionary.search("b..")) # 返回 True