C语言实现Trie树（字典树）：原理与完整代码

晚来风

发布时间：2026-10-13| 4人浏览过

原创

Trie树（字典树）是一种用于高效检索字符串的数据结构。通过共享公共前缀节点，它在词频统计和前缀匹配任务中能显著降低时间复杂度，同时节省内存开销。本文将解析其核心特性，并提供完整的C语言实现方案。

核心概念与特性

Trie树通过树形结构存储字符串集合。以关键词 and, as, at, cn, com 为例，其构建逻辑如下：

从结构中可观察出三个关键特性：

根节点空值：除根节点外，每个子节点仅包含一个字符。
路径构成字符串：从根节点到特定节点的路径上经过的字符连接起来，即为该节点对应的字符串。
公共前缀共享：单词之间的公共前缀在同一个字符节点中保存，避免冗余存储。

应用场景与优势

Trie树主要适用于以下两个场景：

词频统计：相比哈希表或堆，Trie树利用公共前缀压缩空间，特别适合内存受限环境下的海量文本处理。
前缀匹配：若需获取所有以 "a" 开头的字符串，传统朴素做法的时间复杂度为 O(N²)；而使用Trie树仅需遍历树深 h（h为检索单词长度），实现近乎秒级的检索效果。

第1步：定义数据结构

首先定义Trie节点的结构体，通常只支持小写字母时，数组大小为26即可。

#define MAX 26 // 字符集大小
 
typedef struct trieNode {
    struct trieNode *next[MAX];
    int count; // 记录以该节点结尾的词出现次数
} trieNode;

第2步：实现初始化操作

创建根节点并分配内存，将子节点指针全部置空，计数归零。

/** 
 * 初始化Trie树根结点 
 */ 
void initTrie(trieNode **root) 
{
    int i;
   
    *root = (trieNode *)malloc(sizeof(trieNode));
    (*root)->count = 0;
   
    for (i = 0; i < MAX; i ++) {
        (*root)->next[i] = NULL;
    }
}

第3步：实现单词插入

遍历待插入字符串的每个字符：若当前路径不存在，则新建节点并初始化为NULL指针，计数设为1；若存在，则沿路径下移并将节点计数加1。

/** 
 * Trie树插入操作 
 */ 
void insert(char *str, trieNode *root) 
{
    int i;
   
    trieNode *p = root;
   
    while (*str != '\0') {
        if (p->next[*str - 'a'] == NULL) {
            trieNode *tmp = (trieNode *)malloc(sizeof(trieNode));
            for (i = 0; i < MAX; i ++) {
                tmp->next[i] = NULL;
            }
            tmp->count = 1;
            p->next[*str - 'a'] = tmp;
            p = p->next[*str - 'a'];
        } else {
            p = p->next[*str - 'a'];
            p->count ++;
        }
   
        str ++;
    }
}

第4步：实现计数查询

查找给定前缀在树中出现的次数。若中途发现节点为空，说明前缀不存在，返回0；否则到达终点后返回节点的计数值。

/** 
 * 统计前缀出现次数 
 */ 
int count(char *search, trieNode *root) 
{
    trieNode *p = root;
   
    while (*search != '\0') {
        if (p->next[*search - 'a'] == NULL) {
            return 0;
        } else {
            p = p->next[*search - 'a'];
            search ++;
        }
    }
   
    return p->count;
}

第5步：清理内存与主函数测试

为避免内存泄漏，必须递归释放所有子节点。以下为完整的AC代码示例，包含初始化和测试循环。

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
 
#define MAX 26 // 字符集大小 
 
typedef struct trieNode { 
    struct trieNode *next[MAX]; 
    int count; // 记录该字符出现次数 
} trieNode; 
 
 
/** 
 * 初始化Trie树根结点 
 */ 
void initTrie(trieNode **root) 
{
    int i;
 
    *root = (trieNode *)malloc(sizeof(trieNode));
    (*root)->count = 0;
 
    for (i = 0; i < MAX; i ++) {
        (*root)->next[i] = NULL;
    }
}

/** 
 * Trie树插入操作 
 */ 
void insert(char *str, trieNode *root) 
{
    int i;
 
    trieNode *p = root;
 
    while (*str != '\0') {
        if (p->next[*str - 'a'] == NULL) {
            trieNode *tmp = (trieNode *)malloc(sizeof(trieNode));
            for (i = 0; i < MAX; i ++) {
                tmp->next[i] = NULL;
            }
            tmp->count = 1;
            p->next[*str - 'a'] = tmp;
            p = p->next[*str - 'a'];
        } else {
            p = p->next[*str - 'a'];
            p->count ++;
        }
 
        str ++;
    }
}

/** 
 * 统计前缀出现次数 
 */ 
int count(char *search, trieNode *root) 
{
    trieNode *p = root;
 
    while (*search != '\0') {
        if (p->next[*search - 'a'] == NULL) {
            return 0;
        } else {
            p = p->next[*search - 'a'];
            search ++;
        }
    }
 
    return p->count;
}

/** 
 * 清理trie树 
 */ 
void delTrie(trieNode *root) 
{
    int i;
 
    for (i = 0; i < MAX; i ++) {
        if (root->next[i] != NULL) {
            delTrie(root->next[i]);
        }
    }
 
    free(root);
}

 
int main(void) 
{
    char str[15];
    trieNode *root;
 
    // 初始化根结点 
    initTrie(&root);
 
    // 读取单词并插入 
    while (gets(str) && str[0] != '\0') {
        insert(str, root);
    }
 
    // 读取前缀并统计出现次数 
    while (gets(str) && str[0] != '\0') {
        printf("%d\n", count(str, root));
    }
 
    delTrie(root);
 
    return 0;
}