讲师中心 微信公众号

工具推荐

视频效率加速
立刻MV
立刻MV

低成本歌曲 MV、视频生成

updream

一键生成高质量推广成片

Laper
Laper

剧本策划到成片协作

AniShort
AniShort

AI短剧协同制作平台

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

风杰酱_1251

风杰酱_1251

发布时间:2025-12-20 17:13:02

|

779人浏览过

|

来源于php中文网

原创

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

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

什么是Trie树(字典树)

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

基础节点设计与插入逻辑

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

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

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

前缀匹配与单词搜索实现

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

立即学习“C++免费学习笔记(深入)”;

Password Generator
Password Generator

当用户请求生成密码、创建PIN、制作助记词、检查密码强度、生成API密钥、创建安全令牌、管理密码创意时

下载

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

  • 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++速学教程(入门到精通)
c++速学教程(入门到精通)

c++怎么学习?c++怎么入门?c++在哪学?c++怎么学才快?不用担心,这里为大家提供了c++速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热门AI工具

更多
蛙蛙写作

一款AI论文写作工具,主要用于超级AI智能写作助手,适合需要提升相关任务效率的用户。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

讯飞绘文

讯飞绘文是一款由科大讯飞推出的一站式 AIGC 内容运营平台。

墨刀AI
墨刀AI Hot

一款AI图像与设计工具,主要用于产品经理的专属智能体,适合需要提升相关任务效率的用户。

SoundView
SoundView Hot

SoundView是一款面向跨境电商的视频翻译、配音和本地化 AI 创作平台。

立刻MV
立刻MV Hot

立刻MV是一款AI文本写作工具,AI 音乐视频(MV)创作工具。

Lovart
Lovart Hot

一款面向视觉设计创作的AI设计平台,可通过智能体和画布工作流辅助制作海报、Logo、网页、PPT及其他视觉内容。

相关专题

更多
string转int
string转int

在编程中,我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算,或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

7639

2023.08.02

c语言const用法
c语言const用法

const是关键字,可以用于声明常量、函数参数中的const修饰符、const修饰函数返回值、const修饰指针。详细介绍:1、声明常量,const关键字可用于声明常量,常量的值在程序运行期间不可修改,常量可以是基本数据类型,如整数、浮点数、字符等,也可是自定义的数据类型;2、函数参数中的const修饰符,const关键字可用于函数的参数中,表示该参数在函数内部不可修改等等。

2478

2023.09.20

js 字符串转数组
js 字符串转数组

js字符串转数组的方法:1、使用“split()”方法;2、使用“Array.from()”方法;3、使用for循环遍历;4、使用“Array.split()”方法。本专题为大家提供js字符串转数组的相关的文章、下载、课程内容,供大家免费下载体验。

1958

2023.08.03

js截取字符串的方法
js截取字符串的方法

js截取字符串的方法有substring()方法、substr()方法、slice()方法、split()方法和slice()方法。本专题为大家提供字符串相关的文章、下载、课程内容,供大家免费下载体验。

3224

2023.09.04

java基础知识汇总
java基础知识汇总

java基础知识有Java的历史和特点、Java的开发环境、Java的基本数据类型、变量和常量、运算符和表达式、控制语句、数组和字符串等等知识点。想要知道更多关于java基础知识的朋友,请阅读本专题下面的的有关文章,欢迎大家来php中文网学习。

6424

2023.10.24

字符串介绍
字符串介绍

字符串是一种数据类型,它可以是任何文本,包括字母、数字、符号等。字符串可以由不同的字符组成,例如空格、标点符号、数字等。在编程中,字符串通常用引号括起来,如单引号、双引号或反引号。想了解更多字符串的相关内容,可以阅读本专题下面的文章。

6649

2023.11.24

java读取文件转成字符串的方法
java读取文件转成字符串的方法

Java8引入了新的文件I/O API,使用java.nio.file.Files类读取文件内容更加方便。对于较旧版本的Java,可以使用java.io.FileReader和java.io.BufferedReader来读取文件。在这些方法中,你需要将文件路径替换为你的实际文件路径,并且可能需要处理可能的IOException异常。想了解更多java的相关内容,可以阅读本专题下面的文章。

8154

2024.03.22

php中定义字符串的方式
php中定义字符串的方式

php中定义字符串的方式:单引号;双引号;heredoc语法等等。想了解更多字符串的相关内容,可以阅读本专题下面的文章。

12734

2024.04.29

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

140

2026.11.12

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
WebSocket手册
WebSocket手册

共0课时 | 0人学习

HTML5/CSS3/JavaScript/ES6入门课程
HTML5/CSS3/JavaScript/ES6入门课程

共102课时 | 11.2万人学习

前端基础到实战(HTML5+CSS3+ES6+NPM)
前端基础到实战(HTML5+CSS3+ES6+NPM)

共162课时 | 29.2万人学习

关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn