字典树又称前缀树，是一种专门用于高效存储和检索字符串集合的树形数据结构，其核心思想是利用字符串的公共前缀来减少存储空间并加速查询：每个节点代表一个字符，从根节点到任意节点的路径构成一个字符串前缀，通过共享前缀分支来优化存储，并支持快速的插入、查找和前缀匹配操作，广泛应用于搜索引擎自动补全、拼写检查和IP路由等场景。本节的代码模板将向您展示如何通过数组模拟来实现字典树。
数组模拟的特点是内存管理高效、实现简单、性能稳定，适用于只需基本插入查询的场景。相较于链表模拟实现字典树来说，其缺点也可见一斑：存在功能有限、内存固定、不支持删除和重复字符串，扩展性差等问题。
1. C/C++版代码：
// 数组模拟字典树
#include <iostream>
#include <string>
using namespace std;
const int MAXN = 26; // 字符集大小：仅支持26个小写字母
const int MAXM = 100000; // 最大节点数：限制字典树容量防止越界
int trie[MAXM][MAXN]; // 字典树主体：trie[p][c]表示节点p通过字符c到达的子节点编号
bool end[MAXM]; // 结束标志：end[p]=true表示节点p是某个单词的结尾
int cnt = 1; // 已使用节点数：从1开始分配，0作为根节点（空串）
// 插入字符串到字典树
void insert(const string& s) {
int p = 0; // 从根节点（节点0）开始遍历
for (char ch : s) {
int c = ch - 'a'; // 将字符映射到0-25的索引
if (!trie[p][c]) { // 如果当前字符对应的子节点不存在
if (cnt >= MAXM) return; // 容量检查：超出最大节点数则提前返回
trie[p][c] = cnt++; // 分配新节点：将下一个可用节点编号赋给当前路径
}
p = trie[p][c]; // 移动到子节点：继续处理下一个字符
}
end[p] = true; // 标记终点：字符串最后一个字符所在的节点为单词结尾
}
// 查询字符串是否存在于字典树
bool search(const string& s) {
int p = 0; // 从根节点开始遍历
for (char ch : s) {
int c = ch - 'a'; // 字符映射
if (!trie[p][c]) return false; // 路径中断：某个字符对应的节点不存在，字符串不存在
p = trie[p][c]; // 移动到子节点
}
return end[p]; // 路径完整：检查终点节点是否被标记为单词结尾
}2. Java版代码：
// 数组模拟字典树
public class ArrayTrie {
// 字符集大小：仅支持26个小写字母
private static final int MAXN = 26;
// 最大节点数：限制字典树容量防止越界
private static final int MAXM = 100000;
// 字典树主体：trie[p][c]表示节点p通过字符c到达的子节点编号
private static int[][] trie = new int[MAXM][MAXN];
// 结束标志：end[p]=true表示节点p是某个单词的结尾
private static boolean[] end = new boolean[MAXM];
// 已使用节点数：从1开始分配，0作为根节点（空串）
private static int cnt = 1;
// 插入字符串到字典树
public static void insert(String s) {
int p = 0; // 从根节点（节点0）开始遍历
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
int c = ch - 'a'; // 将字符映射到0-25的索引
if (trie[p][c] == 0) { // 如果当前字符对应的子节点不存在
if (cnt >= MAXM) return; // 容量检查：超出最大节点数则提前返回
trie[p][c] = cnt++; // 分配新节点：将下一个可用节点编号赋给当前路径
}
p = trie[p][c]; // 移动到子节点：继续处理下一个字符
}
end[p] = true; // 标记终点：字符串最后一个字符所在的节点为单词结尾
}
// 查询字符串是否存在于字典树
public static boolean search(String s) {
int p = 0; // 从根节点开始遍历
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
int c = ch - 'a'; // 字符映射
if (trie[p][c] == 0) return false; // 路径中断：某个字符对应的节点不存在，字符串不存在
p = trie[p][c]; // 移动到子节点
}
return end[p]; // 路径完整：检查终点节点是否被标记为单词结尾
}
// 主函数
public static void main(String[] args) {
// 主函数
}
}3. Python版代码：
# 数组模拟字典树
# 字符集大小：仅支持26个小写字母
MAXN = 26
# 最大节点数：限制字典树容量防止越界
MAXM = 100000
# 字典树主体：trie[p][c]表示节点p通过字符c到达的子节点编号
trie = [[0] * MAXN for _ in range(MAXM)]
# 结束标志：end[p]=True表示节点p是某个单词的结尾
end = [False] * MAXM
# 已使用节点数：从1开始分配，0作为根节点（空串）
cnt = 1
# 插入字符串到字典树
def insert(s):
global cnt
p = 0 # 从根节点（节点0）开始遍历
for ch in s:
c = ord(ch) - ord('a') # 将字符映射到0-25的索引
if trie[p][c] == 0: # 如果当前字符对应的子节点不存在
if cnt >= MAXM: # 容量检查：超出最大节点数则提前返回
return
trie[p][c] = cnt # 分配新节点：将下一个可用节点编号赋给当前路径
cnt += 1
p = trie[p][c] # 移动到子节点：继续处理下一个字符
end[p] = True # 标记终点：字符串最后一个字符所在的节点为单词结尾
# 查询字符串是否存在于字典树
def search(s):
p = 0 # 从根节点开始遍历
for ch in s:
c = ord(ch) - ord('a') # 字符映射
if trie[p][c] == 0: # 路径中断：某个字符对应的节点不存在，字符串不存在
return False
p = trie[p][c] # 移动到子节点
return end[p] # 路径完整：检查终点节点是否被标记为单词结尾
# 主函数
def main():
pass # 主函数
if __name__ == "__main__":
main()
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程