Trie树、字典树、前缀树
个人认为这种树最好的叫法叫前缀树，比较好理解。
前缀树一般用来处理string查找问题，是一种高效的处理字符串相关问题的树形数据结构。
典型应用场景
trie树本人见过的最典型的应用就是在web路由匹配查找上，路由一般包括了很多字符串，并且需要和路由对应的处理函数绑定，请求也非常频繁，所以用trie树来处理还是比较高效的。
原理以及代码实现
trie树有一个根节点，这个节点一般不放任何数据。每个节点都有26个孩子，对应26个英文字母，节点存放的数据为一个一个英文字母。当当前节点到根节点能组成一个单词时做上标记，代表这是一个单词的结尾。每个string可以共享节点。
节点结构体
struct Node{
string word;
int count; //记录相同单词的个数
Node* child[26]; //孩子节点 26个字母
};
//初始化
void Clear(Node* node){
for(int i=0;i<26;i++){
node->child[i]=NULL;
}
node->count=0;
node->word="";
}
插入单词
//插入单词
void Insert(Node* root,string word){
Node* node = root;
for(int i=0;i<word.length();i++){
if(node->child[word[i]-'a']==NULL){
node->child[word[i]-'a'] = new Node;
Clear(node->child[word[i]-'a']);
}
node = node->child[word[i]-'a'];
}
node->word = word;
node->count+=1;
}
寻找带有前缀的单词节点
//寻找前缀节点
Node* search_pre(Node* root,string pre){
Node* node = root;
for(int i=0;i<pre.length();i++){
if(node->child[pre[i]-'a']==NULL)
return NULL;
node = node->child[pre[i]-'a']; //移到孩子节点上继续遍历
}
return node;
}
计算单词出现的次数
//寻找单词 返回单词数量 (是寻找前缀的一个特例)
int search_word(Node* root,string word){
Node* node = search_pre(root,word);
if(node!=NULL)
return node->count;
else
return 0;
}
打印单词
//根据节点打印全部单词
void print_all(Node* node){
if(node==NULL)
return;
if(node->count>0)
cout<<node->word<<endl;
//继续递归打印子节点
for(int i=0;i<26;i++){
print_all(node->child[i]);
}
}
//根据前缀打印全部单词
void print_pre(Node* root,string pre){
Node* node = root;
for(int i=0;i<pre.length();i++){
if(node->child[pre[i]-'a']==NULL){
cout<<"没有前缀"<<endl;
return;
}
node = node->child[pre[i]-'a'];
}
print_all(node);
}
删除单词
删除单词有两种情况
- 如果此单词尾部节点没有其他单词需要共享的节点，直接删除，节省空间
- 有其他单词共享字母节点，那就只清除单词标记
bool has_child(Node* node){
for(int i=0;i<26;i++){
if(node->child[i]!=NULL)
return true;
}
return false;
}
void DeleteWord(Node* node,string word,int lv){
if(lv==word.length() && node){
//清空节点
node->word="";
if(node->count==0){
cout<<"没有单词";
return;
}
node->count-=1;
if(!has_child(node)){
// delete node;
node = NULL;
}
}else{
DeleteWord(node->child[word[lv]-'a'],word,lv+1);
//清空单词标记
if(node){
node->word="";
node->count-=0;
if(!has_child(node)){
//delete node; //象征性的删除
node = NULL;
}
}
}
}
完整可运行代码
#include<iostream>
using namespace std;
struct Node{
string word;
int count; //记录相同单词的个数
Node* child[26]; //孩子节点 26个字母
};
void Clear(Node* node){
for(int i=0;i<26;i++){
node->child[i]=NULL;
}
node->count=0;
node->word="";
}
//插入单词
void Insert(Node* root,string word){
Node* node = root;
for(int i=0;i<word.length();i++){
if(node->child[word[i]-'a']==NULL){
node->child[word[i]-'a'] = new Node;
Clear(node->child[word[i]-'a']);
}
node = node->child[word[i]-'a'];
}
node->word = word;
node->count+=1;
}
//寻找前缀节点
Node* search_pre(Node* root,string pre){
Node* node = root;
for(int i=0;i<pre.length();i++){
if(node->child[pre[i]-'a']==NULL)
return NULL;
node = node->child[pre[i]-'a']; //移到孩子节点上继续遍历
}
return node;
}
//寻找单词 返回单词数量 (是寻找前缀的一个特例)
int search_word(Node* root,string word){
Node* node = search_pre(root,word);
if(node!=NULL)
return node->count;
else
return 0;
}
//根据节点打印全部单词
void print_all(Node* node){
if(node==NULL)
return;
if(node->count>0)
cout<<node->word<<endl;
//继续递归打印子节点
for(int i=0;i<26;i++){
print_all(node->child[i]);
}
}
//根据前缀打印全部单词
void print_pre(Node* root,string pre){
Node* node = root;
for(int i=0;i<pre.length();i++){
if(node->child[pre[i]-'a']==NULL){
cout<<"没有前缀"<<endl;
return;
}
node = node->child[pre[i]-'a'];
}
print_all(node);
}
bool has_child(Node* node){
for(int i=0;i<26;i++){
if(node->child[i]!=NULL)
return true;
}
return false;
}
void DeleteWord(Node* node,string word,int lv){
if(lv==word.length() && node){
//清空节点
node->word="";
if(node->count==0){
cout<<"没有单词";
return;
}
node->count-=1;
if(!has_child(node)){
// delete node;
node = NULL;
}
}else{
DeleteWord(node->child[word[lv]-'a'],word,lv+1);
//清空单词标记
if(node){
node->word="";
node->count-=0;
if(!has_child(node)){
//delete node; //象征性的删除
node = NULL;
}
}
}
}
int main(){
Node* root = new Node;
Clear(root);
Insert(root,"hello");
Insert(root,"hello");
Insert(root,"haha");
Insert(root,"he");
Insert(root,"case");
Insert(root,"cat");
Insert(root,"biningo");
cout<<search_word(root,"hello")<<endl;
DeleteWord(root,"hello",0);
cout<<search_word(root,"hello")<<endl;
DeleteWord(root,"hello",0);
cout<<search_word(root,"hello")<<endl;
DeleteWord(root,"hello",0);
cout<<search_word(root,"hello")<<endl;
}