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

c++怎么实现一个Trie树（字典树）_c++字典树Trie的结构与实现方法

尼克

发布： 2025-11-04 15:36:02

原创

688人浏览过

Trie树通过共享前缀高效处理字符串操作。1. 结构上每个节点含26个子指针和isEnd标记，表示字符路径与单词结尾；2. Trie类实现insert插入字符路径并标记结尾，search逐层匹配且检查isEnd确保完整单词，startsWith仅判断前缀路径存在性；3. 示例中插入"apple"和"app"后，search与startsWith正确返回布尔结果；4. 优化建议包括用map支持更大字符集、添加析构函数释放内存，适用于自动补全等场景。核心在于路径即字符串的逻辑，需注意isEnd设置细节。

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

实现一个Trie树（字典树）在C++中主要用于高效处理字符串相关问题，比如前缀匹配、单词查找等。它的核心思想是利用字符串的公共前缀来减少查询时间。

1. Trie树的基本结构

Trie树是一种多叉树结构，每个节点代表一个字符，从根到某节点的路径构成一个字符串前缀。通常设计如下：

每个节点包含一个子节点数组（或map），用于指向下一个字符。
一个布尔标记，表示该节点是否为某个单词的结尾。

假设只处理小写字母 a-z，可以用大小为26的指针数组来表示子节点。

定义节点结构如下：

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

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

登录后复制

};

2. Trie类的设计与实现

封装TrieNode，提供插入、查找和前缀判断功能。

腾讯智影-AI数字人

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

查看详情

class Trie {
private:
    TrieNode* root;
<p>public:
Trie() {
root = new TrieNode();
}</p><pre class='brush:php;toolbar:false;'>// 插入一个单词
void insert(const string& word) {
    TrieNode* node = root;
    for (char c : word) {
        int idx = c - 'a';
        if (!node->children[idx]) {
            node->children[idx] = new TrieNode();
        }
        node = node->children[idx];
    }
    node->isEnd = true;
}

// 查找是否完整存在某个单词
bool search(const string& word) {
    TrieNode* node = root;
    for (char c : word) {
        int idx = c - 'a';
        if (!node->children[idx]) {
            return false;
        }
        node = node->children[idx];
    }
    return node->isEnd;
}

// 判断是否存在以prefix为前缀的单词
bool startsWith(const string& prefix) {
    TrieNode* node = root;
    for (char c : prefix) {
        int idx = c - 'a';
        if (!node->children[idx]) {
            return false;
        }
        node = node->children[idx];
    }
    return true;
}

登录后复制

};

3. 使用示例

下面是一个简单使用方式：

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
<pre class='brush:php;toolbar:false;'>cout << trie.search("app") << endl;        // 输出 1 (true)
cout << trie.search("apple") << endl;      // 输出 1 (true)
cout << trie.startsWith("ap") << endl;     // 输出 1 (true)
cout << trie.search("apply") << endl;      // 输出 0 (false)

return 0;

登录后复制

}