c++如何实现一个简单的Trie树(字典树)_c++前缀匹配与字符串搜索【数据结构】

Trie树是一种用于高效字符串前缀操作的树形结构，节点代表字符、路径构成字符串，共享公共前缀以节省空间；支持O(L)插入、搜索与前缀匹配，常用于自动补全和拼写检查。

什么是Trie树（字典树）

Trie树是一种专门用于高效处理字符串前缀操作的树形结构，常用于自动补全、拼写检查、IP路由查找等场景。它的核心特点是：每个节点代表一个字符，从根到某节点的路径构成一个字符串；所有公共前缀共享同一段路径，节省空间且加速前缀匹配。

基础节点设计与插入逻辑

每个节点不需要存字符本身（由父节点到子节点的边隐式表示），只需记录子节点指针和是否为单词结尾。C++中常用red">unordered_map或固定大小数组（如TrieNode* children[26]）实现子节点映射。

插入字符串时，从根出发，逐字符向下走：若对应子节点不存在则新建；遍历完所有字符后，将末节点的isEnd设为true。

• 只处理小写字母时，可用children[c - 'a']快速索引
• 支持任意ASCII字符，推荐用unordered_map避免空间浪费
• 插入过程时间复杂度为O(L)，L为字符串长度

前缀匹配与单词搜索实现

搜索一个完整单词，需走到末节点且该节点isEnd == true；判断是否存在某前缀，只需成功走到对应位置即可，不要求isEnd为真。

立即学习“C++免费学习笔记（深入）”；

例如：已插入"apple"、"app"，那么search("app")返回true，startsWith("appl")也返回true。

Supermeme

Supermeme是一个AI驱动的Meme生成器，可以快速生成有趣的Meme梗图

114

查看详情

• search()：遍历字符，中途遇到空指针返回false；结束时检查isEnd
• startsWith()：同样遍历，但只需确认能走完全程，不检查isEnd
• 两者都不修改结构，纯读操作，线性时间完成

完整可运行示例（小写英文版）

以下是一个轻量、无内存泄漏风险的实现，含构造、插入、搜索、前缀判断功能：

class Trie {
  struct TrieNode {
    TrieNode* children[26] = {}; // 初始化为nullptr
    bool isEnd = false;
  };
  TrieNode* root;
public:
  Trie() : root(new TrieNode()) {}
  void insert(const string& word) {
    TrieNode* p = root;
    for (char c : word) {
      if (!p->children[c - 'a']) p->children[c - 'a'] = new TrieNode();
      p = p->children[c - 'a'];
    }
    p->isEnd = true;
  }
  bool search(const string& word) {
    TrieNode* p = root;
    for (char c : word) {
      if (!p->children[c - 'a']) return false;
      p = p->children[c - 'a'];
    }
    return p->isEnd;
  }
  bool startsWith(const string& prefix) {
    TrieNode* p = root;
    for (char c : prefix) {
      if (!p->children[c - 'a']) return false;
      p = p->children[c - 'a'];
    }
    return true;
  }
};

注意：实际工程中建议补充析构函数释放内存，或改用智能指针；若需支持Unicode或多语言，应替换为unordered_map等方案。

基本上就这些 —— Trie树不复杂但容易忽略细节，比如isEnd标记位置、大小写处理、边界空字符串判断等，写对了前缀匹配效率就稳了。

以上就是c++++如何实现一个简单的Trie树(字典树)_c++前缀匹配与字符串搜索【数据结构】的详细内容，更多请关注php中文网其它相关文章！