第1章 字典树（Trie）：从零开始构建你的单词搜索引擎

大家好，我是你们的老朋友。今天咱们来聊聊字典树——一个我工作中几乎天天打交道的结构。

说实话，我第一次接触 Trie 是在做英文单词联想输入的时候。当时用户敲几个字母，系统就得快速给出候选词。用哈希表？不行，前缀匹配太慢。用数组？更别提了。后来翻到《算法导论》里关于 Trie 的介绍，一拍大腿——就是它了。

1.1 字典树的定义与结构

字典树，也叫前缀树（Prefix Tree），是一种专门处理字符串集合的树形结构。它的核心思想是：利用字符串的公共前缀来节省存储空间，同时加速查找。

你想想看，如果我们要存 "cat"、"car"、"dog" 这三个词，用哈希表得存三个独立的字符串。但用 Trie，它们共享 "ca" 这个前缀，只分叉到 't' 和 'r'。是不是很巧妙？

下面是我画的一张 Trie 结构图，展示了插入 "cat"、"car"、"dog" 后的样子：

1.2 插入操作

插入操作其实很简单。从根节点开始，逐个字符往下走：

• 如果当前字符对应的子节点存在，就沿着它继续
• 如果不存在，就创建一个新节点
• 处理完最后一个字符后，把当前节点的 is_end 标记设为 true

来看代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALPHABET_SIZE 26

typedef struct TrieNode {
    struct TrieNode *children[ALPHABET_SIZE];
    int is_end;  // 1 表示是一个完整单词的结尾
} TrieNode;

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

void insert(TrieNode *root, const char *word) {
    TrieNode *cur = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int idx = word[i] - 'a';
        if (cur->children[idx] == NULL) {
            cur->children[idx] = create_node();
        }
        cur = cur->children[idx];
    }
    cur->is_end = 1;
}

嗯，这里要注意：我假设输入都是小写字母。如果包含大写或特殊字符，你得调整索引映射。我在项目中遇到过有人直接拿 ASCII 码当索引，结果数组开得巨大无比，内存直接爆了。

1.3 查找操作

查找分两种：精确查找和前缀查找。

精确查找：沿着路径走完所有字符，最后检查 is_end 是否为 true。

前缀查找：沿着路径走完所有字符，只要路径存在就返回 true，不管 is_end。

// 精确查找：判断 word 是否在字典中
int search(TrieNode *root, const char *word) {
    TrieNode *cur = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int idx = word[i] - 'a';
        if (cur->children[idx] == NULL) {
            return 0;  // 路径不存在
        }
        cur = cur->children[idx];
    }
    return cur->is_end;  // 必须是完整单词
}

// 前缀查找：判断是否有以 prefix 开头的单词
int starts_with(TrieNode *root, const char *prefix) {
    TrieNode *cur = root;
    for (int i = 0; prefix[i] != '\0'; i++) {
        int idx = prefix[i] - 'a';
        if (cur->children[idx] == NULL) {
            return 0;
        }
        cur = cur->children[idx];
    }
    return 1;  // 路径存在即返回真
}

1.4 字典树的应用场景

说白了，Trie 就是为字符串匹配而生的。我总结了一下，主要有三大应用：

1.4.1 单词统计

你可以用 Trie 来统计每个单词出现的次数。只需要在节点里加一个 count 字段，插入时每经过一个节点就加 1，最后在 is_end 节点记录完整单词的次数。

我在做英文词频统计时用过这个方案。相比哈希表，Trie 能同时支持前缀统计——比如统计所有以 "pre" 开头的单词出现次数，哈希表就做不到了。

1.4.2 前缀匹配

这是 Trie 的看家本领。搜索引擎的自动补全、输入法的联想词、IDE 的代码补全，底层基本都是 Trie。

举个例子：用户输入 "app"，系统要快速给出 "apple"、"application"、"appointment" 等候选词。用 Trie 找到 "app" 节点后，DFS 遍历所有子节点就能拿到所有候选词。

1.4.3 字符串排序

Trie 天然支持字典序排序。你只需要先序遍历整棵树，按字符顺序访问子节点，输出的就是字典序排列。

我记得有一次需要给 10 万个英文单词排序。用快排？O(n log n)。用 Trie？O(n * L)，L 是平均单词长度。对于长单词多的场景，Trie 明显更快。

// 先序遍历输出所有单词（字典序）
void print_sorted(TrieNode *root, char *buffer, int depth) {
    if (root->is_end) {
        buffer[depth] = '\0';
        printf("%s\n", buffer);
    }
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (root->children[i] != NULL) {
            buffer[depth] = 'a' + i;
            print_sorted(root->children[i], buffer, depth + 1);
        }
    }
}

好了，字典树的基础内容就聊到这儿。代码虽然简单，但背后的思想很强大。下次你写搜索框自动补全的时候，不妨试试自己手写一个 Trie——相信我，比调第三方库有意思多了。

---

公众号：蓝海资料掘金营，微信 deep3321