例题"/>
字典树模板及例题
转载：Trie树的常见应用大总结（面试+附代码实现）
（一）Trie的简介
Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。他的核心思想是空间换时间，空间消耗大但是插入和查询有着很优秀的时间复杂度。
（二）Trie的定义
Trie树的键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀（prefix）,从根节点到当前结点的路径上的所有字母组成当前位置的字符串，结点可以保存当前字符串、出现次数、指针数组(指向子树)以及是否是结尾标志等等。
struct Trie
{
int count;//前缀出现的次数
struct Trie *next[SIZE];//孩子节点的数目
bool isEnd; //判断到这个位置是否是一个单词
string name;
Trie()//构造函数
{
count=0;
memset(next,0,sizeof(next));
isEnd=false;
name.clear();
}
};
Trie树可以利用字符串的公共前缀来节约存储空间，如下图所示：
它有3个基本性质：
(1) 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
(2) 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
(3) 每个节点的所有子节点包含的字符都不相同。
（三）Trie树的基本操作
（1）插入操作
按下标索引逐个插入字母，若当前字母存在则继续下一个，否则new出当前字母的结点，所以插入的时间复杂度只和字符串的长度n有关，为O(n)。
void Insert(string s)
{
int len=s.length();
int pos;
struct Trie *u=root;
for(int i=0;i<len;i++)
{
pos=s[i]-'0';
if(u->next[pos]==NULL)//数字在边上，或者说是以位置的方式体现，不需要存储
u->next[pos]=new Trie;
u=u->next[pos];
u->count++;
}
u->isEnd=true;//表明为一个单词的节点
u->name=s;//同时存储单词
}
（2）查询操作
和插入操作相仿，若查询途中某一个结点并不存在，则直接就return返回。否则继续下去，当字符串结束时，trie树上也有结束标志，那么证明此字符串存在，return true；
int Search(string s)
{
struct Trie *u=root;
int len=s.length();
for(int i=0;i<len;i++)
{
int pos=s[i]-'0';
if(u->next[pos]==NULL)
return 0;
else
u=u->next[pos];
}
return u->count;
}
（3）删除操作
一般来说，对Trie单个结点的删除操作不常见，所以我在这里也只提供递归删除整个树的操作
void del(struct Trie *u)
{
for(int i=0;i<SIZE;i++)
{
if(u->next[i]!=NULL)
del(u->next[i]);
}
delete(u);
}
（4）遍历操作
如果我们想要将trie中的字符串排序输出，直接先序遍历即可。
void print(struct Trie *u)
{
if(u->isEnd)
cout<<u->name<<":"<<u->count<<endl;
for(int i=0;i<SIZE;i++)
if(u->next[i]!=NULL)
print(u->next[i]);
}
上面整体的模板：
#include<iostream>
#include<cstring>
using namespace std;const int SIZE=10;
struct Trie
{int count;//前缀出现的次数struct Trie *next[SIZE];//孩子节点的数目 bool isEnd; //判断到这个位置是否是一个单词string name; Trie()//构造函数 {count=0;memset(next,0,sizeof(next));isEnd=false;}
}; struct Trie *root=new Trie;//建立根节点void Insert(string s)
{int len=s.length();int pos;struct Trie *u=root;for(int i=0;i<len;i++){pos=s[i]-'0';if(u->next[pos]==NULL)//数字在边上，或者说是以位置的方式体现，不需要存储 u->next[pos]=new Trie;u=u->next[pos];u->count++; }u->isEnd=true;//表明为一个单词的节点u->name=s;//同时存储单词
} int Search(string s)
{struct Trie *u=root;int len=s.length();for(int i=0;i<len;i++){int pos=s[i]-'0';if(u->next[pos]==NULL)return 0;elseu=u->next[pos];}return u->count;
} void del(struct Trie *u)
{for(int i=0;i<SIZE;i++){if(u->next[i]!=NULL)del(u->next[i]);}delete(u);
}void print(struct Trie *u)
{if(u->isEnd)cout<<u->name<<":"<<u->count<<endl;for(int i=0;i<SIZE;i++)if(u->next[i]!=NULL)print(u->next[i]);
}int main()
{int n;string s;cin>>n;while(n--){cin>>s;Insert(s);}print(root);//打印检查下 del(root);//释放树，下次重新建立 return 0;
}
对于不同的题目，将模板稍微改动就好。
下面是一个例题，用来判断是否存在前缀。
来源：POJ3630 HDU1671 ZOJ2876 UVA11362 Phone List【字典树】
代码：
#include<iostream>
#include<cstring>
using namespace std;const int SIZE=10;
struct Trie
{int count;//前缀出现的次数struct Trie *next[SIZE];//孩子节点的数目 bool isEnd; //判断到这个位置是否是一个单词string name; Trie()//构造函数 {count=0;memset(next,0,sizeof(next));isEnd=false;name.clear();}
}; struct Trie *root=new Trie;//建立根节点bool Insert(string s)
{int len=s.length();int pos;struct Trie *u=root;for(int i=0;i<len;i++){pos=s[i]-'0';if(u->next[pos]==NULL)//数字在边上，或者说是以位置的方式体现，不需要存储 u->next[pos]=new Trie;u=u->next[pos];u->count++;if(u->count>1&&u->isEnd==true)//如果出现前缀问题 return false; }u->isEnd=true;//表明为一个单词的节点u->name=s;//同时存储单词 if(u->count>1&&u->isEnd==true)//如果出现前缀问题 return false; return true;
} int Search(string s)
{struct Trie *u=root;int len=s.length();for(int i=0;i<len;i++){int pos=s[i]-'0';if(u->next[pos]==NULL)return 0;elseu=u->next[pos];}return u->count;
} void del(struct Trie *u)
{for(int i=0;i<SIZE;i++){if(u->next[i]!=NULL)del(u->next[i]);}delete(u);
}void print(struct Trie *u)
{if(u->isEnd)cout<<u->name<<":"<<u->count<<endl;for(int i=0;i<SIZE;i++)if(u->next[i]!=NULL)print(u->next[i]);
}int main()
{int t,n;bool flag;string s;cin>>t;while(t--){flag=true;//开始没有前缀 cin>>n;while(n--){cin>>s;if(flag)if(!Insert(s)) flag=false;}//print(root);//打印检查下 if(flag)cout<<"YES"<<endl;elsecout<<"NO"<<endl;del(root);//释放树，下次重新建立 }return 0;
}
阅读文章：hdu1251-字符前缀查找问题 map容器
#include<iostream>
#include<string>
#include<map>
using namespace std;
int main()
{
string str,str1;
map<string, int> map1;
while(getline(cin, str)&& str.length() !=0)
{
for(int i = 1; i != str.size()+1; i++)
{
str1 = str.substr(0, i); //把当作字典的单词从第一个字母依次增长的往后复制在map中
map1[str1]++;
}
}
while(cin >> str)
{
cout << map1[str] << endl;
}
}
——————————————
参考文章：
字典树(Trie树)实现与应用
Trie树的常见应用大总结（面试+附代码实现）
更多推荐
字典树模板及例题
发布评论