​字典树（前缀树）链表实现代码模板（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] = '\0';
        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("匹配成功。\n\n");
            } else {
                printf("匹配失败，不存在%d个\"%s\"\n\n", num, x);
            }
        } else if (order == 'u') {
            printf("请输入要插入的字符串与数目：");
            scanf("%s%d", x, &num);
            update(x, num);
            printf("%d个\"%s\"已加入字典树。\n\n", num, x);
        } else if (order == 'd') {
            printf("请输入要删除的字符串与数目：");
            scanf("%s%d", x, &num);
            if (!search(x, num)) {
                printf("树中无%d个字符串\"%s\"，请重新键入命令！\n\n", num, x);
                continue;
            }
            erase(x, num);
            printf("%d个\"%s\"已从字典树中删除。\n\n", num, x);
        } else if (order == 'p') {
            printf("当前字典树内有如下字符串：\n");
            temp[0] = '\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：退出程序\n\n");
        }
    }
    
    // 程序结束前清理内存
    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\"\n\n", 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\"已加入字典树。\n\n", 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\"，请重新键入命令！\n\n", num, x);
                    continue;
                }
                erase(x, num);
                System.out.printf("%d个\"%s\"已从字典树中删除。\n\n", num, x);
            } else if (order == 'p') {
                System.out.println("当前字典树内有如下字符串：");
                temp[0] = '\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] * 256
def init_charmapping():
    """初始化字符映射"""
    # 初始化所有字符为无效值
    global charmapping
    charmapping = [-1] * 256
    # 只允许输入小写字符组成的字符串
    for i in range(ord('a'), ord('z') + 1):
        charmapping[i] = i - ord('a')
maxn = 26
class treenode:
    """字典树节点定义"""
    def __init__(self):
        self.count = 0  # 标志此节点所表示字符串在所有字符串中以前缀形式出现的总次数
        self.next = [None] * maxn
head = treenode()
def init_trie():
    """初始化字典树"""
    global head
    head.count = 1  # 初始化为1包括空串并且避免树头被删
    for i in range(maxn):
        head.next[i] = None
def createnew():
    """申请一个新结点并初始化它"""
    newnode = treenode()
    newnode.count = 0
    for i in range(maxn):
        newnode.next[i] = None
    return newnode
def 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 += num
def 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 >= num
def 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] = None
temp = [''] * 1000
def 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()