字典树（前缀树）数组实现代码模板（C/C++/Java/Python多版本）

字典树（前缀树）数组实现代码模板（C/C++/Java/Python多版本）的重点在于把前置条件、操作顺序和容易误判的地方分清楚。

字典树又称前缀树，是一种专门用于高效存储和检索字符串集合的树形数据结构，其核心思想是利用字符串的公共前缀来减少存储空间并加速查询：每个节点代表一个字符，从根节点到任意节点的路径构成一个字符串前缀，通过共享前缀分支来优化存储，并支持快速的插入、查找和前缀匹配操作，广泛应用于搜索引擎自动补全、拼写检查和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()