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

字典树（前缀树）链表实现代码模板（C/C++/Java/Python多版本）需要先看清适用场景和关键步骤，避免只记结论却忽略实际限制。

字典树又称前缀树，是一种专门用于高效存储和检索字符串集合的树形数据结构，其核心思想是利用字符串的公共前缀来减少存储空间并加速查询：每个节点代表一个字符，从根节点到任意节点的路径构成一个字符串前缀，通过共享前缀分支来优化存储，并支持快速的插入、查找和前缀匹配操作，广泛应用于搜索引擎自动补全、拼写检查和IP路由等场景。本节的代码模板将向您展示如何通过链表模拟来实现字典树。

链表模拟的特点是功能丰富、支持删除和重复字符串、内存灵活、扩展性强。相较于数组模拟实现字典树来说，其缺点也不容小觑：存在动态内存分配开销大、代码复杂、存在内存泄漏风险、实现难度较高等问题。

1. C/C++版代码：

// 一个以链表实现带删除功能允许重复字符串的字典树#include <stdio.h>#include <string.h>#include <stdlib.h>int charmapping[256]; // 字符映射数组，-1表示无效字符void init_charmapping() {    // 初始化所有字符为无效值    for (int i = 0; i < 256; i++) {        charmapping[i] = -1;    }    // 只允许输入小写字符组成的字符串    for (int i = 'a'; i <= 'z'; i++) {        charmapping[i] = i - 'a';    }}const int maxn = 26;struct treenode {    int count;    treenode* next[maxn];} head;void init_trie() {    head.count = 1; // 初始化为1包括空串并且避免树头被删    for (int i = 0; i < maxn; i++) {        head.next[i] = NULL;    }}treenode* createnew() {    treenode* newnode = (treenode*)malloc(sizeof(treenode));    newnode->count = 0;    for (int i = 0; i < maxn; i++) {        newnode->next[i] = NULL;    }    return newnode;}void update(char* s, int num) {    int k = 0;    treenode* t = &head;    while (s[k]) {        int temp = charmapping[(unsigned char)s[k]];        if (temp < 0) { // 非法字符            k++;            continue;        }        t->count += num;        if (!t->next[temp]) {            t->next[temp] = createnew();        }        t = t->next[temp];        k++;    }    t->count += num;}bool search(char* s, int num) {    int k = 0;    treenode* t = &head;    while (s[k]) {        int temp = charmapping[(unsigned char)s[k]];        if (temp < 0 || !t->next[temp] || t->next[temp]->count < num) {            return false;        }        t = t->next[temp];        k++;    }    int snum = t->count;    for (int i = 0; i < maxn; i++) {        if (t->next[i]) {            snum -= t->next[i]->count;        }    }    return snum >= num;}//删除函数void erase(char* s, int num) {    if (!search(s, num)) {        return;    }        // 先减少所有相关节点的计数    int k = 0;    treenode* t = &head;    head.count -= num;        while (s[k]) {        int temp = charmapping[(unsigned char)s[k]];        if (temp < 0 || !t->next[temp]) {            break;        }        t->next[temp]->count -= num;        t = t->next[temp];        k++;    }        // 当前实现只减少计数，不实际释放节点，避免内存管理问题}// 递归释放所有节点void free_trie(treenode* node) {    if (!node) return;    for (int i = 0; i < maxn; i++) {        if (node->next[i]) {            free_trie(node->next[i]);            node->next[i] = NULL;        }    }    if (node != &head) {        free(node);    }}char temp[1000];void printall(treenode* tnode, int pos) {    if (!tnode) return;        int count = tnode->count;    for (int i = 0; i < maxn; i++) {        if (tnode->next[i]) {            count -= tnode->next[i]->count;        }    }        for (int i = 0; i < count; i++) {        temp[pos] = '';        printf(""%s"n", temp);    }        for (int i = 'a'; i <= 'z'; i++) {        int idx = charmapping[i];        if (idx >= 0 && tnode->next[idx]) {            temp[pos] = (char)i;            printall(tnode->next[idx], pos + 1);        }    }}int main() {    init_charmapping();    init_trie();        char x[1000];    char order;    int num;        printf("q：查询n");    printf("u：插入n");    printf("d：删除n");    printf("p：打印字典树n");    printf("e：退出n");        while (1) {        printf("n请输入命令：");        fflush(stdout);        scanf(" %c", &order);  // 注意：%c前面的空格可以跳过空白字符                if (order == 'q') {            printf("请输入要查找的字符串与数目：");            scanf("%s%d", x, &num);            if (search(x, num)) {                printf("匹配成功。nn");            } else {                printf("匹配失败，不存在%d个"%s"nn", num, x);            }        } else if (order == 'u') {            printf("请输入要插入的字符串与数目：");            scanf("%s%d", x, &num);            update(x, num);            printf("%d个"%s"已加入字典树。nn", num, x);        } else if (order == 'd') {            printf("请输入要删除的字符串与数目：");            scanf("%s%d", x, &num);            if (!search(x, num)) {                printf("树中无%d个字符串"%s"，请重新键入命令！nn", num, x);                continue;            }            erase(x, num);            printf("%d个"%s"已从字典树中删除。nn", num, x);        } else if (order == 'p') {            printf("当前字典树内有如下字符串：n");            temp[0] = '';            printall(&head, 0);        } else if (order == 'e') {            printf("退出ing....n");            break;        } else {            printf("无效命令,请重新输入！n");            printf("命令q：查询是否存在字符串n");            printf("命令u：往字典树加入字符串n");            printf("命令d：删除某个字符串n");            printf("命令p：按字典序升序输出字典树n");            printf("命令e：退出程序nn");        }    }        // 程序结束前清理内存    free_trie(&head);    return 0;}

2. Java版代码：

// 一个以链表实现带删除功能允许重复字符串的字典树import java.util.Scanner;public class LinkedListTrie {    // 字符映射数组，-1表示无效字符    private static int[] charmapping = new int[256];        // 初始化字符映射    static void init_charmapping() {        // 初始化所有字符为无效值        for (int i = 0; i < 256; i++) {            charmapping[i] = -1;        }        // 只允许输入小写字符组成的字符串        for (int i = 'a'; i <= 'z'; i++) {            charmapping[i] = i - 'a';        }    }        private static final int maxn = 26;        // 字典树节点定义    static class treenode {        int count; // 标志此节点所表示字符串在所有字符串中以前缀形式出现的总次数        treenode[] next;                treenode() {            count = 0;            next = new treenode[maxn];        }    }        private static treenode head = new treenode();        // 初始化字典树    static void init_trie() {        head.count = 1; // 初始化为1包括空串并且避免树头被删        for (int i = 0; i < maxn; i++) {            head.next[i] = null;        }    }        // 申请一个新结点并初始化它    static treenode createnew() {        treenode newnode = new treenode();        newnode.count = 0;        for (int i = 0; i < maxn; i++) {            newnode.next[i] = null;        }        return newnode;    }        // 向字典树添加num个字符串s    static void update(String s, int num) {        int k = 0;        treenode t = head;        while (k < s.length()) {            int temp = charmapping[s.charAt(k)];            if (temp < 0) { // 非法字符                k++;                continue;            }            t.count += num;            if (t.next[temp] == null) {                t.next[temp] = createnew();            }            t = t.next[temp];            k++;        }        t.count += num;    }        // 查找字典树中是否已经存在num个字符串s    static boolean search(String s, int num) {        int k = 0;        treenode t = head;        while (k < s.length()) {            int temp = charmapping[s.charAt(k)];            if (temp < 0 || t.next[temp] == null || t.next[temp].count < num) {                return false;            }            t = t.next[temp];            k++;        }        int snum = t.count;        for (int i = 0; i < maxn; i++) {            if (t.next[i] != null) {                snum -= t.next[i].count;            }        }        return snum >= num;    }        // 删除字典树中的num个字符串s    static void erase(String s, int num) {        if (!search(s, num)) {            return;        }                // 先减少所有相关节点的计数        int k = 0;        treenode t = head;        head.count -= num;                while (k < s.length()) {            int temp = charmapping[s.charAt(k)];            if (temp < 0 || t.next[temp] == null) {                break;            }            t.next[temp].count -= num;            t = t.next[temp];            k++;        }                // 当前实现只减少计数，不实际释放节点，避免内存管理问题    }        // 递归释放所有节点    static void free_trie(treenode node) {        if (node == null) return;        for (int i = 0; i < maxn; i++) {            if (node.next[i] != null) {                free_trie(node.next[i]);                node.next[i] = null;            }        }    }        private static char[] temp = new char[1000];        // 递归打印字典树，打出的就是字典序升序的    static void printall(treenode tnode, int pos) {        if (tnode == null) return;                int count = tnode.count;        for (int i = 0; i < maxn; i++) {            if (tnode.next[i] != null) {                count -= tnode.next[i].count;            }        }                for (int i = 0; i < count; i++) {            System.out.println(""" + new String(temp, 0, pos) + """);        }                for (int i = 'a'; i <= 'z'; i++) {            int idx = charmapping[i];            if (idx >= 0 && tnode.next[idx] != null) {                temp[pos] = (char)i;                printall(tnode.next[idx], pos + 1);            }        }    }        public static void main(String[] args) {        init_charmapping(); // 初始化映射        init_trie();        // 初始化字典树                Scanner scanner = new Scanner(System.in);        String x;        char order; // 命令        int num;    // 数目                System.out.println("q：查询");        System.out.println("u：插入");        System.out.println("d：删除");        System.out.println("p：打印字典树");        System.out.println("e：退出");                while (true) {            System.out.print("n请输入命令：");            String input = scanner.nextLine().trim();            if (input.isEmpty()) continue;                        order = input.charAt(0);                        if (order == 'q') {                System.out.print("请输入要查找的字符串与数目：");                x = scanner.next();                num = scanner.nextInt();                scanner.nextLine(); // 消耗换行符                                if (search(x, num)) {                    System.out.println("匹配成功。n");                } else {                    System.out.printf("匹配失败，不存在%d个"%s"nn", num, x);                }            } else if (order == 'u') {                System.out.print("请输入要插入的字符串与数目：");                x = scanner.next();                num = scanner.nextInt();                scanner.nextLine(); // 消耗换行符                                update(x, num);                System.out.printf("%d个"%s"已加入字典树。nn", num, x);            } else if (order == 'd') {                System.out.print("请输入要删除的字符串与数目：");                x = scanner.next();                num = scanner.nextInt();                scanner.nextLine(); // 消耗换行符                                if (!search(x, num)) {                    System.out.printf("树中无%d个字符串"%s"，请重新键入命令！nn", num, x);                    continue;                }                erase(x, num);                System.out.printf("%d个"%s"已从字典树中删除。nn", num, x);            } else if (order == 'p') {                System.out.println("当前字典树内有如下字符串：");                temp[0] = '';                printall(head, 0);            } else if (order == 'e') {                System.out.println("退出ing....");                break;            } else {                System.out.println("无效命令,请重新输入！");                System.out.println("命令q：查询是否存在字符串");                System.out.println("命令u：往字典树加入字符串");                System.out.println("命令d：删除某个字符串");                System.out.println("命令p：按字典序升序输出字典树");                System.out.println("命令e：退出程序n");            }        }                scanner.close();        // 清空引用        free_trie(head);    }}

3. Python版代码：

# 一个以链表实现带删除功能允许重复字符串的字典树# 字符映射数组，-1表示无效字符charmapping = [-1] * 256def init_charmapping():    """初始化字符映射"""    # 初始化所有字符为无效值    global charmapping    charmapping = [-1] * 256    # 只允许输入小写字符组成的字符串    for i in range(ord('a'), ord('z') + 1):        charmapping[i] = i - ord('a')maxn = 26class treenode:    """字典树节点定义"""    def __init__(self):        self.count = 0  # 标志此节点所表示字符串在所有字符串中以前缀形式出现的总次数        self.next = [None] * maxnhead = treenode()def init_trie():    """初始化字典树"""    global head    head.count = 1  # 初始化为1包括空串并且避免树头被删    for i in range(maxn):        head.next[i] = Nonedef createnew():    """申请一个新结点并初始化它"""    newnode = treenode()    newnode.count = 0    for i in range(maxn):        newnode.next[i] = None    return newnodedef update(s, num):    """向字典树添加num个字符串s"""    k = 0    t = head    while k < len(s):        temp = charmapping[ord(s[k])]        if temp < 0:  # 非法字符            k += 1            continue        t.count += num        if t.next[temp] is None:            t.next[temp] = createnew()        t = t.next[temp]        k += 1    t.count += numdef search(s, num):    """查找字典树中是否已经存在num个字符串s"""    k = 0    t = head    while k < len(s):        temp = charmapping[ord(s[k])]        if temp < 0 or t.next[temp] is None or t.next[temp].count < num:            return False        t = t.next[temp]        k += 1    snum = t.count    for i in range(maxn):        if t.next[i] is not None:            snum -= t.next[i].count    return snum >= numdef erase(s, num):    """删除字典树中的num个字符串s"""    if not search(s, num):        return        # 先减少所有相关节点的计数    k = 0    t = head    head.count -= num        while k < len(s):        temp = charmapping[ord(s[k])]        if temp < 0 or t.next[temp] is None:            break        t.next[temp].count -= num        t = t.next[temp]        k += 1        # 当前实现只减少计数，不实际释放节点，避免内存管理问题def free_trie(node):    """递归释放所有节点"""    if node is None:        return    for i in range(maxn):        if node.next[i] is not None:            free_trie(node.next[i])            node.next[i] = Nonetemp = [''] * 1000def printall(tnode, pos):    """递归打印字典树，打出的就是字典序升序的"""    if tnode is None:        return        count = tnode.count    for i in range(maxn):        if tnode.next[i] is not None:            count -= tnode.next[i].count        for i in range(count):        print(f'"{("".join(temp[:pos]))}"')        for i in range(ord('a'), ord('z') + 1):        idx = charmapping[i]        if idx >= 0 and tnode.next[idx] is not None:            temp[pos] = chr(i)            printall(tnode.next[idx], pos + 1)def main():    """主函数"""    init_charmapping()  # 初始化映射    init_trie()         # 初始化字典树        print("q：查询")    print("u：插入")    print("d：删除")    print("p：打印字典树")    print("e：退出")        while True:        try:            print("n请输入命令：", end="")            command = input().strip()            if not command:                continue                        order = command[0]                        if order == 'q':                print("请输入要查找的字符串与数目：", end="")                try:                    parts = input().strip().split()                    if len(parts) < 2:                        continue                    x = parts[0]                    num = int(parts[1])                except:                    continue                                if search(x, num):                    print("匹配成功。n")                else:                    print(f"匹配失败，不存在{num}个"{x}"n")                                elif order == 'u':                print("请输入要插入的字符串与数目：", end="")                try:                    parts = input().strip().split()                    if len(parts) < 2:                        continue                    x = parts[0]                    num = int(parts[1])                except:                    continue                                update(x, num)                print(f"{num}个"{x}"已加入字典树。n")                            elif order == 'd':                print("请输入要删除的字符串与数目：", end="")                try:                    parts = input().strip().split()                    if len(parts) < 2:                        continue                    x = parts[0]                    num = int(parts[1])                except:                    continue                                if not search(x, num):                    print(f"树中无{num}个字符串"{x}"，请重新键入命令！n")                    continue                erase(x, num)                print(f"{num}个"{x}"已从字典树中删除。n")                            elif order == 'p':                print("当前字典树内有如下字符串：")                temp[0] = ''                printall(head, 0)                            elif order == 'e':                print("退出ing....")                break                            else:                print("无效命令,请重新输入！")                print("命令q：查询是否存在字符串")                print("命令u：往字典树加入字符串")                print("命令d：删除某个字符串")                print("命令p：按字典序升序输出字典树")                print("命令e：退出程序n")                        except EOFError:            break        # 程序结束前清理内存    free_trie(head)if __name__ == "__main__":    main()