C语言字典树详解（从零开始掌握Trie树实现与字符串前缀匹配）

什么是字典树？

字典树（Trie）是一种树形数据结构，专门用于存储字符串集合。它的核心思想是：利用字符串的公共前缀来减少存储空间并提高查询效率。

例如，单词 "apple"、"app"、"apply" 共享前缀 "app"，在字典树中只需存储一次 "app"，后续分支再分别处理不同后缀。

字典树的基本结构

每个字典树节点通常包含以下信息：

• 指向子节点的指针数组（通常大小为26，对应26个小写字母）
• 一个布尔值，标记当前节点是否为某个单词的结尾

下面是我们用C语言定义的字典树节点结构：

#include <stdio.h>#include <stdlib.h>#include <string.h>#define ALPHABET_SIZE 26typedef struct TrieNode {    struct TrieNode* children[ALPHABET_SIZE];    int isEndOfWord; // 1 表示是单词结尾，0 表示不是} TrieNode;

创建新节点

我们需要一个函数来动态分配并初始化一个新的字典树节点：

TrieNode* createNode() {    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));    if (!node) return NULL;    node->isEndOfWord = 0;    for (int i = 0; i < ALPHABET_SIZE; i++) {        node->children[i] = NULL;    }    return node;}

插入单词

插入操作从根节点开始，逐字符遍历单词。如果当前字符对应的子节点不存在，则创建它；最后将最后一个字符的节点标记为单词结尾。

void insert(TrieNode* root, const char* word) {    TrieNode* current = root;    int len = strlen(word);    for (int i = 0; i < len; i++) {        int index = word[i] - 'a'; // 假设输入全是小写字母        if (index < 0 || index >= ALPHABET_SIZE) continue; // 简单错误处理        if (current->children[index] == NULL) {            current->children[index] = createNode();        }        current = current->children[index];    }    current->isEndOfWord = 1;}

搜索单词

搜索过程类似插入：逐字符向下查找。若某字符路径不存在，返回 false；若完整走完路径，还需检查最后一个节点是否被标记为单词结尾。

int search(TrieNode* root, const char* word) {    TrieNode* current = root;    int len = strlen(word);    for (int i = 0; i < len; i++) {        int index = word[i] - 'a';        if (index < 0 || index >= ALPHABET_SIZE || current->children[index] == NULL) {            return 0; // 未找到        }        current = current->children[index];    }    return current != NULL && current->isEndOfWord;}

前缀匹配（SEO关键词：字符串前缀匹配）

字典树的一大优势是能高效判断是否存在以某前缀开头的单词。只需遍历前缀路径，若能完整走完即存在匹配项。

int startsWith(TrieNode* root, const char* prefix) {    TrieNode* current = root;    int len = strlen(prefix);    for (int i = 0; i < len; i++) {        int index = prefix[i] - 'a';        if (index < 0 || index >= ALPHABET_SIZE || current->children[index] == NULL) {            return 0;        }        current = current->children[index];    }    return 1; // 只要路径存在，就说明有以此为前缀的单词}

完整示例程序

下面是一个完整的可运行示例，演示了如何使用我们构建的字典树：

int main() {    TrieNode* root = createNode();    // 插入单词    insert(root, "apple");    insert(root, "app");    insert(root, "apply");    // 搜索测试    printf("Search 'app': %s\n", search(root, "app") ? "Found" : "Not Found");    printf("Search 'apple': %s\n", search(root, "apple") ? "Found" : "Not Found");    printf("Search 'appl': %s\n", search(root, "appl") ? "Found" : "Not Found");    // 前缀匹配测试    printf("Starts with 'ap': %s\n", startsWith(root, "ap") ? "Yes" : "No");    printf("Starts with 'xyz': %s\n", startsWith(root, "xyz") ? "Yes" : "No");    // 注意：实际项目中应释放内存（略）    return 0;}

应用场景与总结

C语言字典树广泛应用于：

• 搜索引擎的自动补全
• 拼写检查器
• IP地址路由（使用二进制Trie）
• 词频统计

通过本教程，你已经掌握了Trie树实现的核心方法，包括节点定义、插入、搜索和字符串前缀匹配。虽然我们只处理了小写字母，但你可以轻松扩展支持大小写、数字甚至Unicode字符。

记住，字典树的空间换时间特性使其在处理大量字符串时极具优势。希望这篇面向小白的教程能帮助你深入理解这一重要的C语言数据结构！