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

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

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

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

基本结构设计

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

struct TrieNode {
    bool isEnd;
    TrieNode* children[26];
TrieNode() {
    isEnd = false;
    for (int i = 0; i < 26; ++i) {
        children[i] = nullptr;
    }
}
};插入字符串
从根节点开始，对每个字符计算其在数组中的索引（如 ch - 'a'），若对应子节点不存在则创建新节点。遍历完所有字符后，标记最后一个节点为结束节点。
立即学习“C++免费学习笔记（深入）”；

							
								
								
									ProcessOn
									免费在线流程图思维导图，专业强大的作图工具，支持多人实时在线协作
								
								下载 
							
						
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;
}
查找前缀是否存在
与查找字符串类似，但不需要判断isEnd。只要能完整遍历前缀的所有字符，就说明存在该前缀。
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的设置。