1.字典树的定义
- 字典树是一种多叉树结构，每个节点代表一个字符，从根节点到某个节点的路径表示一个字符串。
- 每个节点包含若干指向子节点的指针，通常使用数组、哈希表或其他数据结构来实现。
2. 字典树的基本操作
- 插入：将一个字符串插入到字典树中。
- 查找：在字典树中查找一个字符串是否存在。
- 删除：从字典树中删除一个字符串。
3. 字典树的节点结构
struct TrieNode {
TrieNode* children[26]; // 26个英文字母
bool isEndOfWord; // 标记是否是一个单词的结束
};4. 字典树的实现
//插入操作
void insert(string word) {
TrieNode* curr = root;
for (char c : word) {
int index = c - 'a';
if (!curr->children[index]) {
curr->children[index] = new TrieNode();
}
curr = curr->children[index];
}
curr->isEndOfWord = true; // 标记单词结束
}//查找操作
bool search(string word) {
TrieNode* curr = root;
for (char c : word) {
int index = c - 'a';
if (!curr->children[index]) {
return false; // 字符不存在
}
curr = curr->children[index];
}
return curr != nullptr && curr->isEndOfWord; // 判断是否是一个完整的单词
}//删除操作部分
//辅助函数，判断是否有子节点
bool nodeIsEmpty(TrieNode* node) {
for (int i = 0; i < 26; i++) {
if (node->children[i]) {
return false; // 仍有子节点，不能删除
}
}
return true; // 没有子节点，可以删除
}
bool deleteWord(string word, int depth, TrieNode* node) {
if (depth == word.length()) {
if (!node->isEndOfWord) {
return false; // 单词不存在
}
node->isEndOfWord = false; // 标记单词结束
return nodeIsEmpty(node); // 判断当前节点是否可以删除
}
int index = word[depth] - 'a';
if (!node->children[index]) {
return false; // 字符不存在
}
// 递归删除下一个字符
if (deleteWord(word, depth + 1, node->children[index])) {
delete node->children[index]; // 删除节点
node->children[index] = nullptr;
// 如果当前节点没有子节点并且不是单词的结束，则可以删除
return !node->isEndOfWord && nodeIsEmpty(node);
}
return false;
}完整代码，写成类的形式：
#include <iostream>
#include <string>
using namespace std;
struct TrieNode {
TrieNode* children[26];
bool isEndOfWord;
TrieNode() {
isEndOfWord = false;
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* curr = root;
for (char c : word) {
int index = c - 'a';
if (!curr->children[index]) {
curr->children[index] = new TrieNode();
}
curr = curr->children[index];
}
curr->isEndOfWord = true;
}
bool search(string word) {
TrieNode* curr = root;
for (char c : word) {
int index = c - 'a';
if (!curr->children[index]) {
return false;
}
curr = curr->children[index];
}
return curr != nullptr && curr->isEndOfWord;
}
bool deleteWord(string word) {
return deleteWordHelper(word, 0, root);
}
private:
bool deleteWordHelper(string word, int depth, TrieNode* node) {
if (depth == word.length()) {
if (!node->isEndOfWord) {
return false;
}
node->isEndOfWord = false;
return nodeIsEmpty(node);
}
int index = word[depth] - 'a';
if (!node->children[index]) {
return false;
}
if (deleteWordHelper(word, depth + 1, node->children[index])) {
delete node->children[index];
node->children[index] = nullptr;
return !node->isEndOfWord && nodeIsEmpty(node);
}
return false;
}
bool nodeIsEmpty(TrieNode* node) {
for (int i = 0; i < 26; i++) {
if (node->children[i]) {
return false;
}
}
return true;
}
};P1. 洛谷p1481魔族密码
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
int finalans=0;
int curans=0;
using namespace std;
struct TrieNode {
TrieNode* children[26];
bool isEndOfWord;
bool visited;
TrieNode() {
isEndOfWord = false;
visited=0;
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* curr = root;
for (char c : word) {
int index = c - 'a';
if (!curr->children[index]) {
curr->children[index] = new TrieNode();
}
curr = curr->children[index];
}
curr->isEndOfWord = true;
}
bool search(string word) {
TrieNode* curr = root;
for (char c : word) {
int index = c - 'a';
if (!curr->children[index]) {
return false;
}
curr = curr->children[index];
}
return curr != nullptr && curr->isEndOfWord;
}
bool deleteWord(string word) {
return deleteWordHelper(word, 0, root);
}
void dfs(TrieNode* cur)
{
if(cur->visited==1) return;
cur->visited=1;
if(cur->isEndOfWord==true)
{
curans++;
finalans=max(finalans,curans);
//cout<<"当前搜到有效单词尾:"<<"当前ans是:"<<finalans<<endl;
}
for(int i=0;i<25;i++)
{
if(cur->children[i]) dfs(cur->children[i]);
}
if(cur->isEndOfWord==true) curans--;
}
void dfs()
{
dfs(root);
}
private:
bool deleteWordHelper(string word, int depth, TrieNode* node) {
if (depth == word.length()) {
if (!node->isEndOfWord) {
return false;
}
node->isEndOfWord = false;
return nodeIsEmpty(node);
}
int index = word[depth] - 'a';
if (!node->children[index]) {
return false;
}
if (deleteWordHelper(word, depth + 1, node->children[index])) {
delete node->children[index];
node->children[index] = nullptr;
return !node->isEndOfWord && nodeIsEmpty(node);
}
return false;
}
bool nodeIsEmpty(TrieNode* node) {
for (int i = 0; i < 26; i++) {
if (node->children[i]) {
return false;
}
}
return true;
}
};
int main()
{
int n;cin>>n;
vector<string> inputs;
for(int i=1;i<=n;i++)
{
string p;cin>>p;
inputs.push_back(p);
}
Trie mytree=Trie();
for(int i=0;i<inputs.size();i++)
{
mytree.insert(inputs[i]);
}
mytree.dfs();
cout<<finalans;
return 0;
}标签：1.4,index,node,curr,STL,word,C++,return,children From： https://blog.csdn.net/William_Edmund/article/details/142894261