C语言Trie树详解（从零开始掌握字符串高效查找的利器）

如上图所示，单词 "cat"、"car" 和 "cart" 共享前缀 "ca"，Trie树通过这种方式节省空间并加速查找。

Trie树的基本结构

在C语言中，我们可以用结构体来定义Trie节点。每个节点通常包含：

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

下面是我们定义的Trie节点结构：

#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;

创建新节点

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

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;}

插入单词到Trie树

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

void insert(TrieNode* root, const char* word) {    TrieNode* current = root;    for (int i = 0; word[i] != '\0'; i++) {        int index = word[i] - 'a'; // 假设只处理小写字母        if (current->children[index] == NULL) {            current->children[index] = createNode();        }        current = current->children[index];    }    current->isEndOfWord = 1;}

查找单词是否存在

查找过程与插入类似，沿着字符路径向下走。如果中途遇到空指针，说明单词不存在；如果走完所有字符且最后一个节点标记为单词结尾，则存在。

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

完整示例程序

下面是一个完整的C语言Trie树应用示例，演示了插入和查找功能：

int main() {    TrieNode* root = createNode();    // 插入一些单词    insert(root, "hello");    insert(root, "world");    insert(root, "hi");    insert(root, "help");    // 查找测试    printf("Search 'hello': %s\n", search(root, "hello") ? "Found" : "Not Found");    printf("Search 'he': %s\n", search(root, "he") ? "Found" : "Not Found");    printf("Search 'help': %s\n", search(root, "help") ? "Found" : "Not Found");    printf("Search 'helicopter': %s\n", search(root, "helicopter") ? "Found" : "Not Found");    // 注意：实际项目中应释放内存（略）    return 0;}

应用场景与优势

Trie树广泛应用于以下场景：

• 自动补全（如搜索引擎输入建议）
• 拼写检查
• IP路由（最长前缀匹配）
• 词频统计

相比哈希表，Trie树在前缀匹配方面具有天然优势，而且不会出现哈希冲突问题。虽然空间开销略大，但在许多字符串处理任务中，C语言前缀树仍是高效可靠的选择。

总结

通过本文，你已经掌握了Trie树的基本原理和C语言实现方法。无论是面试准备还是实际开发，字符串高效查找都是重要技能。希望你能动手实践，进一步优化这个结构（比如支持大小写、数字或Unicode字符）。

记住，掌握C语言Trie树实现不仅提升你的数据结构能力，还能让你在处理文本数据时更加游刃有余！