字典树模板及例题

Dear 丶 2022-05-11 14:10 198阅读 0赞

转载：[Trie树的常见应用大总结（面试+附代码实现）][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树可以利用字符串的公共前缀来节约存储空间，如下图所示：

![70][]

它有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;
    		else
    			u=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【字典树】][POJ3630 HDU1671 ZOJ2876 UVA11362 Phone List]

![70 1][]

![70 2][]

代码：

#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;
    		else
    			u=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;
    		else
    			cout<<"NO"<<endl;
    			 
    		del(root);//释放树，下次重新建立 
    	}
    	return 0;
    }

阅读文章：[hdu1251-字符前缀查找问题 map容器][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;  
>     \}  
> \}  
> ——————————————[https://blog.csdn.net/imush/article/details/52039806][hdu1251-_ map]

参考文章：

[字典树(Trie树)实现与应用][Trie 1]

[Trie树的常见应用大总结（面试+附代码实现）][Trie]

[Trie]: https://blog.csdn.net/NK_test/article/details/47836119?utm_source=blogxgwz0
[70]: /images/20220505/fa5055a350934e1db248de3a5e32b748.png
[POJ3630 HDU1671 ZOJ2876 UVA11362 Phone List]: https://blog.csdn.net/tigerisland45/article/details/80948189
[70 1]: /images/20220505/12623e61846f4351a6232b6aebbea702.png
[70 2]: /images/20220505/6ec127a0daca481baceee7c6e985e05a.png
[hdu1251-_ map]: https://blog.csdn.net/imush/article/details/52039806
[Trie 1]: https://www.cnblogs.com/xujian2014/p/5614724.html#_label3