在本文中，我们将讨论C++ 中的trie 数据结构及其属性、操作和示例。
Trie 数据结构是一种多路树，用于存储不同的字符串。每个字符串由存储在树状结构（即Trie 数据结构）中的字符组成。它也称为基数树或前缀树或数字树。基本上，“ trie ”一词来自“re trie val”一词，意思是检索或取回某些东西。它用于各种任务，例如拼写检查、搜索单词、自动完成等。
Trie数据结构的性质：
trie 数据结构有多种属性。trie数据结构的一些主要属性如下：
- Trie数据结构是树结构的形式，其中每个节点代表字符串的单个字符，从根到节点覆盖的路径代表特定的字符串。
- trie数据结构从根节点开始，根节点始终为空并表示空字符。从根节点开始，出现各种其他分支，保存字符串的其他字符。
- trie 数据结构中字符串的末尾称为叶节点。每个叶节点可能包含额外的信息。
它可以存储和共享引用共享前缀的字符串的公共初始部分。共享公共前缀可以更轻松地高效搜索一组字符串。Trie 数据结构中的操作：
在 trie 数据结构中可以完成三种操作：
1、插入操作：
该操作用于向Trie中添加一个新节点，即一个新字符串。
2、搜索操作：
该操作用于查找特定字符串并检查它是否存在于Trie 数据结构中。
3、删除操作：
此操作用于删除Trie 数据结构中存在的字符串。
例子：
我们举个例子，用C++实现trie数据结构来执行插入、搜索和删除操作。
include <iostream>
using namespace std;
//Describing the size of the character.
define CHAR_SIZE 128
//Here is a class that can be used to store a Trie node.
class Trie
{
public:
bool isLeaf;
Trie* character[CHAR_SIZE];
Trie()
{
this->isLeaf = false;
for (int k = 0; k< CHAR_SIZE; k++) {
this->character[k] = nullptr;
}
}
void insert(string);
bool search(string);
bool haveChildren(Trie const*);
bool deletion(Trie*&, string);
};
//Here is an iterative function for inserting a key in a Trie.
void Trie::insert(string key)
{
//Beginning from the root node.
Trie* curr = this;
for (int k = 0; k< key.length(); k++)
{
//If the path does not exist, a new node will be created.
if (curr->character[key[k]] == nullptr) {
curr->character[key[k]] = new Trie();
}
//Moving to the next node.
curr = curr->character[key[k]];
}
//Current node is marked as a leaf.
curr->isLeaf = true;
}
bool Trie::search(string key)
{
//If the Trie is empty, then return false.
if (this == nullptr) {
return false;
}
Trie* curr = this;
for (int k = 0; k< key.length(); k++)
{
curr = curr->character[key[k]];
if (curr == nullptr) {
return false;
}
}
return curr->isLeaf;
}
//Determines whether or not a specified node has any child nodes.
bool Trie::haveChildren(Trie const* curr)
{
for (int k = 0; k< CHAR_SIZE; k++)
{
if (curr->character[k]) {
return true; //A child has beenfound.
}
}
return false;
}
//Here is a recursive function that can be used to delete a key from a Trie.
bool Trie::deletion(Trie*& curr, string key)
{
//If the Trie is empty, then return false.
if (curr == nullptr) {
return false;
}
if (key.length())
{
if (curr != nullptr &&
curr->character[key[0]] != nullptr &&
deletion(curr->character[key[0]], key.substr(1)) &&
curr->isLeaf == false)
{
if (!haveChildren(curr))
{
delete curr;
curr = nullptr;
return true;
}
else {
return false;
}
}
}
//If the end of the key has been reached.
if (key.length() == 0 && curr->isLeaf)
{
if (!haveChildren(curr))
{
//Delete the current node.
delete curr;
curr = nullptr;
//Delete the parent nodes that are not at the leaf level.
return true;
}
else {
curr->isLeaf = false;
return false;
}
}
return false;
}
//Trie data structure C++ implementation
int main()
{
Trie* head = new Trie();
head->insert("java");
cout << head->search("java") << " "; //Returns 1 (If found)
head->insert("javatpoint");
cout << head->search("javatpoint") << " "; //Returns1
cout << head->search("javaa") << " "; //Returns0 (If not found)
head->insert("javac");
cout << head->search("javac") << " "; //Returns1
head->insert("j");
cout << head->search("j"); //Returns1
cout << endl;
head->deletion(head, "java");
cout << head->search("java") << " "; //Returns0
cout << head->search("javatpoint") << " "; //Returns1
cout << head->search("javac"); //Returns1
cout << endl;
head->deletion(head, "j");
cout << head->search("j") << " "; //Returns0
cout << head->search("javac") << " "; //Returns1
cout << head->search("javatpoint"); //Returns1
cout << endl;
head->deletion(head, "javatpoint");
cout << head->search("javatpoint") << " "; //Returns0
cout << head->search("javac") << " "; //Returns1
head->deletion(head, "javac");
cout << head->search("javac"); //Returns0
cout << endl;
if (head == nullptr) {
cout << "Empty!!\n"; //Trie is empty now
}
cout << head->search("javac"); //Returns0
return 0;
}
|
上述 C++ 程序的解释：
- 首先，程序中包含 C++ 库。
- 我们假设马可 "CHAR_SIZE "有 128 个字符。
- 我们创建了一个名为 "Trie "的类，该类有四个成员函数：insert、search、haveChildren 和 deletion。
- 插入 "函数用于向 Trie 中添加字符串。
- search "函数用于在 Trie 中搜索字符串，如果发现该字符串，则返回 true。
- haveChildren "函数用于检查给定 Trie 节点中是否有非零的子节点。
- delete "函数是一个递归函数，用于从 Trie 中删除一个字符串。
- 使用 "insert "函数插入各种字符串，包括 "java"、"javatpoint"、"javac "和 "j"。
- 使用 "search"功能检查各种字符串是否存在。搜索字符串 "java "时，返回 true。同样，搜索字符串 "javatpoint "时，返回 true。搜索字符串 "javaa "时，返回 false，因为 Trie 中没有这个字符串。搜索字符串 "javac "时，返回 true；搜索字符串 "j "时，返回 true。
- 然后，使用 "deletion "删除字符串 "java"、"javatpoint"、"javac "和 "j"。
- 删除操作完成后，"search "方法会再次被调用，以验证字符串是否已从 Trie 中成功删除。
- 如果搜索操作成功，找到字符串时返回 1，找不到字符串时返回 0。
- 最终输出将显示 Trie 为空。它会打印 "Empty!!"并返回 O。
结论
在本文中，我们了解了 Trie 数据结构，这是一种存储字符串集合的树状结构。它有多种应用，如单词搜索、拼写检查、自动完成等。我们还了解了 Trie 数据结构的各种操作，包括插入、搜索和删除操作。