C++怎么实现一个Trie树(字典树)_C++数据结构与前缀匹配算法

Trie树通过树形结构高效实现字符串前缀匹配与查找。1. 每个节点包含26个子节点指针和一个结尾标记；2. 插入时逐字符创建路径，末尾标记isEnd；3. 查找需完整匹配且isEnd为true；4. 前缀判断只需路径存在；5. 封装为类便于操作，适用于自动补全等场景。

实现一个 Trie 树（字典树）在 C++ 中非常实用，尤其适用于字符串前缀匹配、自动补全、拼写检查等场景。Trie 树通过将字符串逐字符存储在树结构中，能高效地插入、查找和匹配具有相同前缀的单词。

基本结构设计

每个 Trie 节点包含若干子节点指针和一个标记，表示该节点是否为某个字符串的结尾。

class TrieNode {
public:
    bool isEnd;
    TrieNode* children[26]; // 假设只处理小写字母 a-z
TrieNode() {
    isEnd = false;
    for (int i = 0; i < 26; ++i) {
        children[i] = nullptr;
    }
}
};
这里使用大小为 26 的指针数组来映射 'a' 到 'z'。也可以用 unordered_map 来支持更多字符类型，更灵活但稍慢。
插入字符串
从根节点开始，对字符串中每个字符，计算其在数组中的索引（如 c - 'a'），若对应子节点不存在则创建新节点。遍历完所有字符后，将最后一个节点的 isEnd 设为 true。
void insert(TrieNode* root, 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;
}
查找完整字符串
与插入类似，逐字符向下走。如果中途遇到空指针，说明字符串不存在；若能走完且最后一个节点的 isEnd 为 true，则存在该字符串。
bool search(TrieNode* root, 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;
}
判断是否存在某前缀
只需要检查能否顺着前缀的每个字符走到最后，不要求 isEnd 为 true。
bool startsWith(TrieNode* root, 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;
}
把上面功能封装成一个类会更清晰：
class Trie {
private:
    TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
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;
}

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;
}
};
使用示例：
Trie trie;
trie.insert("apple");
cout << trie.search("apple") << endl;     // 输出 1
cout << trie.search("app") << endl;       // 输出 0
cout << trie.startsWith("app") << endl;   // 输出 1
基本上就这些。注意实际项目中需考虑内存释放问题，可在析构函数中递归删除所有节点。Trie 在处理大量字符串前缀时效率远高于哈希表，虽然空间开销略大，但在搜索性能上有明显优势。
 
		


# word 
# node 
# app 
# c++ 
# apple 
# red 
# 封装 
# 析构函数 
# 字符串 
# 递归 
# char 
# 指针 
# 数据结构 
# 空指针 
# 算法 
# 适用于 
# 不存在 
# 走到 
# 可以用 
# 遍历 
# 只需 
# 但在 
# 设为 
# 上有 
 




相关文章：
 焦点电影公司作品,电影焦点结局是什么？ 
 西安大型网站制作公司,西安招聘网站最好的是哪个？ 
 邀请函制作网站有哪些,有没有做年会邀请函的网站啊？在线制作，模板很多的那种？ 
如何在Windows 2008云服务器安全搭建网站？ 
 网站制作和推广的区别,想自己建立一个网站做推广，有什么快捷方法马上做好一个网站？ 
如何快速搭建安全的FTP站点？ 
实现虚拟支付需哪些建站技术支撑？ 
 北京网站制作费用多少,建立一个公司网站的费用.有哪些部分,分别要多少钱？ 
 网站专业制作公司,网站编辑是做什么的？好做吗？工作前景如何？ 
定制建站方案优化指南：企业官网开发与建站费用解析 
建站之家VIP精选网站模板与SEO优化教程整合指南 
如何快速启动建站代理加盟业务？ 
建站之星安装失败：服务器环境不兼容？ 
 成都网站制作公司哪家好,四川省职工服务网是做什么用？ 
 油猴 教程,油猴搜脚本为什么会网页无法显示？ 
 红河网站制作公司,红河事业单位身份证如何上传？ 
如何在腾讯云服务器上快速搭建个人网站？ 
如何在搬瓦工VPS快速搭建网站？ 
 天河区网站制作公司,广州天河区如何办理身份证？需要什么资料有预约的网站吗？ 
高防服务器：AI智能防御DDoS攻击与数据安全保障 
PHP 500报错的快速解决方法 
实现点击下箭头变上箭头来回切换的两种方法【推荐】 
高性价比服务器租赁——企业级配置与24小时运维服务 
 极客网站有哪些,DoNews、36氪、爱范儿、虎嗅、雷锋网、极客公园这些互联网媒体网站有什么差异？ 
如何通过虚拟机搭建网站？详细步骤解析 
 攀枝花网站建设,攀枝花营业执照网上怎么年审？ 
香港服务器选型指南：免备案配置与高效建站方案解析 
 赚钱网站制作软件,建一个网站怎样才能赚钱?是如何盈利的？ 
如何在Windows虚拟主机上快速搭建网站？ 
建站之星如何优化SEO以实现高效排名？ 
 网站代码制作软件有哪些,如何生成自己网站的代码？ 
建站之星与建站宝盒如何选择最佳方案？ 
建站10G流量真的够用吗？如何应对访问高峰？ 
宝塔建站助手安装配置与建站模板使用全流程解析 
 怎么用手机制作网站链接,dw怎么把手机适应页面变成网页？ 
 网站制作哪家好,cc、.co、.cm哪个域名更适合做网站？ 
 制作网站的软件免费下载,免费制作app哪个平台好？ 
广州营销型建站服务商推荐：技术优势与SEO优化解析 
如何配置支付宝与微信支付功能？ 
如何在香港服务器上快速搭建免备案网站？ 
巅云智能建站系统：可视化拖拽+多端适配+免费模板一键生成 
 长沙做网站要多少钱,长沙国安网络怎么样？ 
如何使用Golang安装API文档生成工具_快速生成接口文档 
建站之星如何防范黑客攻击与数据泄露？ 
如何在IIS服务器上快速部署高效网站？ 
如何用PHP快速搭建高效网站？分步指南 
高配服务器限时抢购：企业级配置与回收服务一站式优惠方案 
 深圳网站制作公司好吗,在深圳找工作哪个网站最好啊？ 
如何快速生成凡客建站的专业级图册？ 
如何快速查询网站的真实建站时间？