湘潭网站建设,酒店类网站建设方案书,可以申请微信号的网站,企业在线设计网站#x1f320;作者#xff1a;阿亮joy. #x1f386;专栏#xff1a;《数据结构与算法要啸着学》 #x1f387;座右铭#xff1a;每个优秀的人都有一段沉默的时光#xff0c;那段时光是付出了很多努力却得不到结果的日子#xff0c;我们把它叫做扎根 目录#x1f449;… 作者阿亮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;vectorstring 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 上的实现前缀树是比我们实现的前缀树是要难度低的所以只需要将上面的代码拷贝过去再将函数名和函数的返回值修改成题目要求的样子就可以通过了。 总结 本篇博客主要讲解了什么是前缀树以及前缀树的实现等。那么以上就是本篇博客的全部内容了如果大家觉得有收获的话可以点个三连支持一下谢谢大家❣️
