C++怎么实现一个Trie树（字典树）_C++数据结构与Trie树实现方法-C++-PHP中文网

C++怎么实现一个Trie树（字典树）_C++数据结构与Trie树实现方法

尼克

发布： 2025-11-15 20:25:02

原创

551人浏览过

答案：Trie树通过节点数组实现字符串高效插入、查找与前缀匹配，支持自动补全等应用，需注意isEnd标记和内存管理。

c++怎么实现一个trie树（字典树）_c++数据结构与trie树实现方法

实现一个Trie树（字典树）在C++中主要用于高效地处理字符串的插入、查找和前缀匹配。它常用于自动补全、拼写检查、IP路由等场景。下面是一个简洁、实用的Trie树实现方法。

基本结构设计

每个Trie节点包含一个布尔值表示是否为某个字符串的结尾，以及一组指向子节点的指针。使用数组或map存储子节点，这里用大小为26的指针数组（假设只处理小写字母）。

struct TrieNode {
    bool isEnd;
    TrieNode* children[26];
<pre class='brush:php;toolbar:false;'>TrieNode() {
    isEnd = false;
    for (int i = 0; i < 26; ++i) {
        children[i] = nullptr;
    }
}

登录后复制

};

插入字符串

从根节点开始，对每个字符计算其在数组中的索引（如 ch - 'a'），若对应子节点不存在则创建新节点。遍历完所有字符后，标记最后一个节点为结束节点。

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

腾讯智影-AI数字人

基于AI数字人能力，实现7*24小时AI数字人直播带货，低成本实现直播业务快速增增，全天智能在线直播

查看详情

void insert(TrieNode* root, const string& word) {
    TrieNode* node = root;
    for (char ch : word) {
        int idx = ch - 'a';
        if (!node->children[idx]) {
            node->children[idx] = new TrieNode();
        }
        node = node->children[idx];
    }
    node->isEnd = true;
}

登录后复制

查找完整字符串

逐字符向下查找，若中途遇到空指针说明字符串不存在。如果顺利走完且最后一个节点标记为isEnd，则说明存在该字符串。

bool search(TrieNode* root, const string& word) {
    TrieNode* node = root;
    for (char ch : word) {
        int idx = ch - 'a';
        if (!node->children[idx]) {
            return false;
        }
        node = node->children[idx];
    }
    return node->isEnd;
}
</font><H3>查找前缀是否存在</H3><p>与查找字符串类似，但不需要判断isEnd。只要能完整遍历前缀的所有字符，就说明存在该前缀。</p><font color="#0000FF"><pre class="brush:php;toolbar:false;">
bool startsWith(TrieNode* root, const string& prefix) {
    TrieNode* node = root;
    for (char ch : prefix) {
        int idx = ch - 'a';
        if (!node->children[idx]) {
            return false;
        }
        node = node->children[idx];
    }
    return true;
}

登录后复制

整个Trie类可以封装成一个类，便于管理内存和调用接口。注意实际项目中建议添加析构函数释放动态分配的节点，避免内存泄漏。这个实现方式简单清晰，适合大多数基础应用场景。基本上就这些，不复杂但容易忽略细节比如isEnd的设置。

以上就是C++怎么实现一个Trie树（字典树）_C++数据结构与Trie树实现方法的详细内容，更多请关注php中文网其它相关文章！