当前位置： 首页 > news >正文

温州大都市建设开发有限公司网站四川仁厚建设集团有限公司

news 2025/9/17 12:07:45
温州大都市建设开发有限公司网站,四川仁厚建设集团有限公司,wordpress微信登录的插件,企业设计网站推荐🌠作者：阿亮joy. 🎆专栏：《数据结构与算法要啸着学》 🎇座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根 目录👉…

🌠作者：@阿亮joy.
🎆专栏：《数据结构与算法要啸着学》
🎇座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根
在这里插入图片描述


目录

    • 👉前缀树的实现👈
      • 什么是前缀树
      • 节点的定义
      • 构造函数
      • 插入字符串
      • 查找字符串和前缀
      • 析构函数
      • 删除字符串
      • 打印前缀树
      • 完整代码
      • OJ题：实现前缀树
    • 👉总结👈

👉前缀树的实现👈

什么是前缀树

Trie（发音类似 “try”），被称为前缀树或字典树，是一种树形的数据结构，可用于高效地存储和检索字符串数据集中的键。这个数据结构有相当多的应用情景，例如自动补完和拼写检查。下图就是经典的前缀树，我们接下来要实现的前缀树的节点存储的数据比较丰富，以达到特定字符串在树中出现几次等类似的功能。

在这里插入图片描述

节点的定义

// 前缀树节点的定义
// 假设字符都是小写字母
struct TrieNode
{int pass = 0;	// 有几个字符串经过该节点(前缀包含这个字符的字符串数量)int end = 0;	// 以该节点为结尾的字符串的数量,如果不允许字符串重复插入,可以改成bool// next[0] == nullptr 表示没有走向'a'的路// next[0] != nullptr 表示有走向'a'的路// ...// next[25] != nullptr 表示有走向'z'的路TrieNode* next[26] = { nullptr };	// 26个空位,准备挂下一个节点'a'-'z',没有挂节点时为nullptr// 如果字符种类个数比较多,可以将数组换成哈希表或者set
};

构造函数

前缀树是用哨兵位头节点来管理整棵前缀树的，所以其构造函数需要 new 上一个哨兵位头节点。

class Trie
{typedef TrieNode Node;
public:Trie(){_root = new Node();}
private:Node* _root = nullptr;	// 哨兵位头节点,可以用来求前缀树中字符串的数量,也可以求空串的数量
};

注：哨兵位头节点的 pass 值可以表示前缀树含有的字符串数量，end 值可以表示前缀树含有空串的数量。因为任何字符串都会以空串作为前缀，都会经过哨兵位头节点。

插入字符串

我们从哨兵位头节点开始，插入字符串。对于当前字符对应的子节点，有以下两种情况：

  • 子节点存在：沿着指针移动到子节点，继续处理下一个字符。
  • 子节点不存在：创建一个新的子节点，记录在 next 指针数组的对应的位置上，然后沿着指针移动到子节点，继续处理下一个字符。
  • 插入字符串的同时，还需要更新沿途节点的 pass 值。

插入字符串图解：

在这里插入图片描述

class Trie
{
public:void Insert(const string& str){Node* cur = _root;++cur->pass;	// 任何一个字符串都需要经过哨兵位头节点for (size_t i = 0; i < str.size(); ++i){size_t index = str[i] - 'a';// 如果之前没有字符串经过该节点,则需要建出新节点if (cur->next[index] == nullptr){cur->next[index] = new Node();}cur = cur->next[index];++cur->pass;}// cur指向字符串的最后一个节点,++cur->end表示多了一个字符串以该节点结尾++cur->end;}
}

如果不需要插入重复字符串，可以将函数的返回值改成 bool 类型。

查找字符串和前缀

class Trie
{
public:// 查找前缀树中有多少个要查找的字符串size_t Search(const string& str) const{Node* cur = _root;for (auto ch : str){// 找的过程发现没路了,说明树中不存在要查找的字符串if (cur->next[ch - 'a'] == nullptr){return 0;}cur = cur->next[ch - 'a'];}// cur是str最后一个字符,cur->end表示树中有多少个strreturn cur->end;}// 查找树中有多少个字符串以前缀prefix为前缀size_t StartsWith(const std::string& prefix) const{Node* cur = _root;for (auto ch : prefix){// 找的过程中发现没有路,则说明没有字符串以prefix为前缀if (cur->next[ch - 'a'] == nullptr){return 0;}cur = cur->next[ch - 'a'];}// cur->pass表示有多少个字符串以prefix为前缀return cur->pass;}
}

注：查找的过程和插入的过程非常的相似，只是查找时发现没有路，就直接返回 0，表示树中没有该字符串或者树中的字符串不以 prefix 为前缀。注：如果树中有要查找的字符串 str，则 cur->end 表示树中有多少个 str；如果树有字符串以 prefix 为前缀，则 cur->pass 表示多少个字符串以 prefix 为前缀。

析构函数

class Trie
{typedef TrieNode Node;
public:~Trie(){Destroy(_root);}
private:void Destroy(Node* root){// 先销毁孩子节点,才能够销毁自己for (int i = 0; i < 26; ++i){// root->next[i]不为空,则说明有节点,需要递归释放节点if (root->next[i] != nullptr){Destroy(root->next[i]);}}delete root;}
}

前缀树析构时，需要先释放孩子节点，才能够释放哨兵位头节点。而孩子节点有可能会有孩子节点，所以我们可以采用递归去释放节点。

删除字符串

class Trie
{typedef TrieNode Node;
public:// 从树中删除字符串str,注：如果有多个str,只会删除一次void Erase(const string& str){// 树中没有str,无法删除if (Search(str) == 0)return;Node* cur = _root;--cur->pass;for (size_t i = 0; i < str.size(); ++i){size_t index = str[i] - 'a';// 如果发现str是唯一经过该节点的字符串// 那么就需要递归去释放当前节点及后续路径的节点if (--cur->next[index]->pass == 0){Destroy(cur->next[index]);	// 递归释放节点cur->next[index] = nullptr;	// next需要置为nullptrreturn;}cur = cur->next[index];}// 如果字符串的所有字符都删除了一遍,还有该路径,那么最后要// --cur->end,表明树中str的个数减少了一个--cur->end;}
}

删除字符串时，需要看树中是否有需要删除的字符串。如果没有，直接 return 即可。如果有，才进行删除。进行删除时，如果发现 str 是唯一经过该节点的字符串，那么就需要递归去释放当前节点及后续路径的节点。

打印前缀树

class Trie
{typedef TrieNode Node;
public:void Print() const{cout << "根节点:[" << "pass: " << _root->pass << " end: " << _root->end << "]" << endl;_Print(_root);}
private:void _Print(Node* root) const{if (root == nullptr)return;for (int i = 0; i < 26; ++i){if (root->next[i] == nullptr)continue;else{cout << "节点" << (char)('a' + i) << ":[pass: " << root->next[i]->pass << " end: " << root->next[i]->end << "]" << endl;_Print(root->next[i]);}}}
}

完整代码

#pragma once#include <vector>
#include <string>
#include <iostream>
using namespace std;// 前缀树节点的定义
// 假设字符都是小写字母
struct TrieNode
{int pass = 0;	// 有几个字符串经过该节点(前缀包含这个字符的字符串数量)int end = 0;	// 以该节点为结尾的字符串的数量,如果不允许重复插入,可以改成bool// next[0] == nullptr 表示没有走向'a'的路// next[0] != nullptr 表示有走向'a'的路// ...// next[25] != nullptr 表示有走向'z'的路TrieNode* next[26] = { nullptr };	// 26个空位,准备挂下一个节点'a'-'z',没有挂节点时为nullptr// 如果字符种类个数比较多,可以将数组换成哈希表或者set
};class Trie
{typedef TrieNode Node;
public:Trie(){_root = new Node();}~Trie(){Destroy(_root);}// 查找前缀树中有多少个要查找的字符串size_t Search(const string& str) const{Node* cur = _root;for (auto ch : str){// 找的过程发现没路了,说明树中不存在要查找的字符串if (cur->next[ch - 'a'] == nullptr){return 0;}cur = cur->next[ch - 'a'];}// cur是str最后一个字符,cur->end表示树中有多少个strreturn cur->end;}// 查找树中有多少个字符串以前缀prefix为前缀size_t StartsWith(const std::string& prefix) const{Node* cur = _root;for (auto ch : prefix){// 找的过程中发现没有路,则说明没有字符串以prefix为前缀if (cur->next[ch - 'a'] == nullptr){return 0;}cur = cur->next[ch - 'a'];}// cur->pass表示有多少个字符串以prefix为前缀return cur->pass;}// 插入字符串void Insert(const string& str){Node* cur = _root;++cur->pass;	// 任何一个字符串都需要经过哨兵位头节点for (size_t i = 0; i < str.size(); ++i){size_t index = str[i] - 'a';// 如果之前没有字符串经过该节点,则需要建出新节点if (cur->next[index] == nullptr){cur->next[index] = new Node();}cur = cur->next[index];++cur->pass;}// cur指向字符串的最后一个节点,++cur->end表示多了一个字符串以该节点结尾++cur->end;}// 从树中删除字符串str,注：如果有多个str,只会删除一次void Erase(const string& str){// 树中没有str,无法删除if (Search(str) == 0)return;Node* cur = _root;--cur->pass;for (size_t i = 0; i < str.size(); ++i){size_t index = str[i] - 'a';// 如果发现str是唯一经过该节点的字符串// 那么就需要递归去释放当前节点及后续路径的节点if (--cur->next[index]->pass == 0){Destroy(cur->next[index]);	// 递归释放节点cur->next[index] = nullptr;	// next需要置为nullptrreturn;}cur = cur->next[index];}// 如果字符串的所有字符都删除了一遍,还有该路径,那么最后要// --cur->end,表明树中str的个数减少了一个--cur->end;}void Print() const{cout << "根节点:[" << "pass: " << _root->pass << " end: " << _root->end << "]" << endl;_Print(_root);}private:void Destroy(Node* root){// 先销毁孩子节点,才能够销毁自己for (int i = 0; i < 26; ++i){if (root->next[i] != nullptr){Destroy(root->next[i]);}}delete root;}void _Print(Node* root) const{if (root == nullptr)return;for (int i = 0; i < 26; ++i){if (root->next[i] == nullptr)continue;else{cout << "节点" << (char)('a' + i) << ":[pass: " << root->next[i]->pass << " end: " << root->next[i]->end << "]" << endl;_Print(root->next[i]);}}}private:Node* _root = nullptr;	// 哨兵位头节点,可以用来求前缀树中字符串的数量,也可以求空串的数量
};

前缀树的测试

void TrieTest()
{Trie t;vector<string> v = { "abc","abd", "abe", "abe", "" ,"a" , "bc", "bd", "be" };for (string& str : v){t.Insert(str);}// 前缀树的打印t.Print();cout << "----------------------" << endl;// 输出空串的数量cout << "空串的数量: " << t.Search("") << endl;// 任意字符串均以空串为前缀/树中字符串的数量cout << "树中字符串的数量: " << t.StartsWith("") << endl;// 以"ab"为前缀的字符串个数cout << "以ab为前缀的字符串个数: " << t.StartsWith("ab") << endl;cout << "----------------------" << endl;// 测试删除for (string& str : v){t.Erase(str);}t.Print();
}

在这里插入图片描述

OJ题：实现前缀树

这里是引用

LeetCode 上的实现前缀树是比我们实现的前缀树是要难度低的，所以只需要将上面的代码拷贝过去，再将函数名和函数的返回值修改成题目要求的样子就可以通过了。

在这里插入图片描述

👉总结👈

本篇博客主要讲解了什么是前缀树以及前缀树的实现等。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️

http://www.yayakq.cn/news/211945/

相关文章：

  • 大学生电子商务专业网站设计如何做好宣传推广
  • 用织梦做的学校网站注册公司费用多少钱
  • 打开上次浏览的网站模板一般的域名可以做彩票网站吗
  • 最有效的网站推广费用wordpress邮件 插件
  • 网站建设域名怎么收费的十堰秦楚网 十堰新闻门户网站
  • php 怎么做网站超链接网站建设项目来源
  • 出口退税备案在哪个网站做赶集网网站建设费用
  • 网站为什么要挂服务器上空间破解网站
  • 最好的网站开发平台建设校园网站
  • 嘉兴企业网站模板建站郑州网站推广专员
  • 网站关键词推广优化中国徐州网官网
  • 最专业的营销网站建设公司排名硬件开发平台有哪些
  • 十堰做网站最专业的公司做电影网站如何买版权
  • ae做动画教程网站个人网站支付解决方案
  • 泰安受欢迎的网站建设做任务反佣金的网站
  • 有人知道做网站吗?大气网站图
  • php 爬取网站所有链接wordpress远程 媒体库
  • 网站运营小结成都十大平面设计工作室
  • 自然堂官方网站建设app界面设计流程
  • 马云的网站怎么做的网上智慧团建系统入口
  • 架设网站是自己架设服务器还是租服务器用ip做网站
  • 义乌网站建设技术托管做网站国内好的服务器
  • 网站 支持建设单位wordpress 设置语言
  • 网站里的图片切换怎么做建设网站知乎
  • 图书租借网站 开发百度一下官网入口
  • 网站的运营费用吗上海集锦信息科技有限公司
  • 网站开发市场网站建设审核
  • 建设集团网站 技术支持中企动力为什么不建议做运维
  • 瑞金网站建设光龙微信优惠券网站怎么做的
  • 扁平化设计网站欣赏怎么做一个软件