C++ Trie树详解（从零实现字典树与前缀匹配）

什么是Trie树？

Trie树是一种树形数据结构，用于存储字符串集合。它的核心思想是：相同前缀的字符串共享相同的路径。例如，单词 "apple" 和 "app" 在Trie中会共享前三个字符 'a' → 'p' → 'p' 的路径。

Trie树的每个节点通常包含：

• 一个布尔值，标记该节点是否为某个单词的结尾
• 一个指针数组（或哈希表），指向子节点（通常对应26个英文字母）

C++实现Trie树

下面我们用C++来实现一个基础的Trie类，支持插入、搜索和前缀匹配三种操作。

#include <iostream>#include <vector>#include <string>using namespace std;class TrieNode {public:    bool isEnd; // 标记是否为单词结尾    vector<TrieNode*> children; // 子节点指针数组    TrieNode() : isEnd(false), children(26, nullptr) {}};class Trie {private:    TrieNode* root;public:    Trie() {        root = new TrieNode();    }    // 插入单词    void insert(const string& word) {        TrieNode* node = root;        for (char c : word) {            int index = c - 'a';            if (!node->children[index]) {                node->children[index] = new TrieNode();            }            node = node->children[index];        }        node->isEnd = true;    }    // 搜索完整单词    bool search(const string& word) {        TrieNode* node = root;        for (char c : word) {            int index = c - 'a';            if (!node->children[index]) {                return false;            }            node = node->children[index];        }        return node->isEnd;    }    // 检查是否存在以prefix开头的单词    bool startsWith(const string& prefix) {        TrieNode* node = root;        for (char c : prefix) {            int index = c - 'a';            if (!node->children[index]) {                return false;            }            node = node->children[index];        }        return true;    }};

使用示例

下面是一个完整的使用示例，展示如何利用我们实现的Trie进行C++字符串处理：

int main() {    Trie trie;    // 插入单词    trie.insert("apple");    trie.insert("app");    trie.insert("application");    // 搜索完整单词    cout << "Search 'app': " << (trie.search("app") ? "Found" : "Not Found") << endl;    cout << "Search 'appl': " << (trie.search("appl") ? "Found" : "Not Found") << endl;    // 前缀匹配    cout << "Starts with 'app': " << (trie.startsWith("app") ? "Yes" : "No") << endl;    cout << "Starts with 'ban': " << (trie.startsWith("ban") ? "Yes" : "No") << endl;    return 0;}

运行结果：

Search 'app': FoundSearch 'appl': Not FoundStarts with 'app': YesStarts with 'ban': No

应用场景与优化方向

Trie树在实际开发中用途广泛：

• 搜索引擎自动补全：用户输入前缀时，快速返回所有可能的完整词
• 拼写检查器：判断用户输入是否存在于词典中
• IP路由查找：最长前缀匹配用于网络数据包转发

当前实现仅支持小写英文字母。若需支持大小写、数字或Unicode字符，可将children改为unordered_map，提升灵活性但略微增加内存开销。

总结

通过本教程，你已经掌握了C++ Trie树的基本原理与实现方法，并了解了其在前缀匹配算法中的强大能力。无论是面试准备还是实际项目开发，Trie都是处理字符串问题的利器。动手试试吧，用它来解决你的C++字符串处理难题！

关键词回顾：C++ Trie树、字典树实现、前缀匹配算法、C++字符串处理