字典树（前缀树）链表实现代码模板（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()