C++ 程序实现 Trie
c++server side programmingprogramming
这里我们将讨论一个 C++ 程序实现 Trie。它是一种基于树的数据结构，用于在大量字符串数据集中高效检索键。
函数和伪代码
开始
函数 insert() :
如果键不存在，则将键插入到 trie 中。如果键是 trie 节点的前缀，则只需标记叶节点。
结束
开始
函数 deleteNode()
如果树为空，则返回 null。
如果正在处理键的最后一个字符，
那么删除该节点后，该节点将不再是字符串的末尾。
如果给定的键不是任何其他字符串的前缀，则删除它并设置 root = NULL。
如果键不是最后一个字符，
然后使用 ASCII 值递归获取子节点。
如果 root 没有剩余子节点并且它不是另一个单词的结尾，
然后删除它并设置 root = NULL。
结束
示例
#include <bits/stdc++.h>
using namespace std;
const int ALPHA_SIZE = 26;
struct Trie {
struct Trie *child[ALPHA_SIZE];
bool endofstring; //如果节点代表单词的结尾，则为真。
};
struct Trie *createNode(void) //创建新节点 {
struct Trie *tNode = new Trie;
tNode->endofstring = false;
for (int i = 0; i < ALPHA_SIZE; i++)
tNode->child[i] = NULL;
return tNode;
}
void insert(struct Trie *root, string key) {
struct Trie *curr = root;
for (int i = 0; i < key.length(); i++) {
int index = key[i] - 'A';
if (!curr->child[index])
curr->child[index] = createNode();
curr = curr->child[index];
}
curr->endofstring= true; //最后一个节点作为叶子
}
bool search(struct Trie *root, string key) { //检查 key 是否存在于 trie 中。如果存在则返回 true
struct Trie *curr = root;
for (int i = 0; i < key.length(); i++) {
int index = key[i] - 'A';
if (!curr->child[index])
return false;
curr = curr->child[index];
}
return (curr != NULL && curr->endofstring);
}
bool isEmpty(Trie* root) //检查 root 是否有子节点 {
for (int i = 0; i < ALPHA_SIZE; i++)
if (root->child[i])
return false;
return true;
}
Trie* removal(Trie* root, string key, intdepth = 0) {
//如果树为空，则返回 null。
if (!root)
return NULL;
if (depth == key.size()) { //如果正在处理键的最后一个字符，
if (root->endofstring)
root->endofstring = false; //则删除该节点后，该节点将不再是字符串的末尾。
if (isEmpty(root)) { //如果给定的键不是任何其他字符串的前缀，
delete (root);
root = NULL;
}
return root;
}
//如果 key 不是最后一个字符，
int index = key[depth] - 'A';
root->child[index] =
deletion(root->child[index], key,depth + 1); //然后使用 ASCII 值对将要获得的子节点进行递归。
if (isEmpty(root) && root->endofstring == false) { //如果 root 没有任何子节点并且它不是另一个单词的结尾
delete (root);
root = NULL;
}
return root;
}
int main() {
string input[] = {"HELLOWORLD","HI","BYE","THE","THENA"}; // 输入键(仅限大写 A 到 Z)
int n = sizeof(inputs)/sizeof(inputs[0]);
struct Trie *root = createNode();
for (int i = 0; i < n; i++)
insert(root, input[i]);
search(root, "HELLOWORLD")? cout << << & ... }
输出
Key is Found Key is not Found Key is deleted
