使用C/C++实现字典树（数组或者链表方式）

目录

1.字典树

2.字典树的实现方式

（1）使用二维数组实现

①字典树的插入

（2）使用链表实现

①定义数据结构

②插入字典树中

③搜索前缀，判断字符串是否存在

④查找前缀数

⑤释放节点

⑥主函数

3.字典树的应用

（1）字符串检索

（2）前缀统计

（3）最长公共前缀

（4）排序

（5）作为其他数据结构与算法的辅助结构

---

1.字典树

字典树，又称为Trie树，单词查找树，是一种树形结构，也是哈希的一种变种，主要用于统计，排序和存储大量的字符串（不限于字符串）。经常被用于搜索引擎引擎系统用于文本词频统计。

字典树特点：主要利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

2.字典树的实现方式

（1）使用二维数组实现

①字典树的插入

将一个字符串插入到字典树中，这里使用二维数组来存储。

初始化工作：

#include<cstring>
#include<iostream>
#include<algorithm>
 
using namespace std;
 
const int maxn=32;
 
//二维数组存储字典树 
int trie[maxn][26];
//字符串的结束标记 
bool end[maxn];
//字符数和索引 
int n,index;
 
void init(){
	memset(trie,0,sizeof(trie));
	memset(end,false,sizeof(end));
	index=1;
}

 比如我们现在插入一个字符串“dream”，因为这里是使用数组存储的，所以需要将字符转换为数字（str[i]-'a'）；这里的trie[1][0]从下标为1开始；首先第一个字符在trie[1][‘d’-'a’];第二个字符在trie[2][‘r’-'a’]；第三个字符在trie[3][‘e’-'a']；第四个字符在trie[4][‘a’-'a']；第五个字符在trie[1][‘m’-'a'].字典树的结构如下：

再插入一个字符串：“draw”,第一个字符在 trie[1][‘d’-'a’]；第二个字符在trie[2][‘r’-'a’]；第是三个字符trie[3][‘a’-'a’]；第四个字符在trie[2][‘w’-'a’]；

 字符串插入操作：

//插入字符串
void insert(string str){
	int p=1;
	for(int i=0;i<str.length();i++){
		int idx=(str[i]-'a');
		//查看当前的位置是否已经存在字符 
		if(trie[p][idx]==0){
			trie[p][idx]=++index;	
		}
		p=trie[p][idx];
	}
	end[p]=true; 
} 

字符串的查找操作：

查找一个字符串是否存在于字典树中，需要将字符串转换为数字，若查找的位置trie[p]['x'-'a']为0，那么则表示没有存储字符串，也就是不存在该字符串。如果查找到最后的结束标志并且字符串也遍历完毕，则表示查找成功。

//搜索当前字符串是否存在
bool search(string str){
	int p=1;
	for(int i=0;i<str.length();i++){
		int idx=str[i]-'a';
		p=trie[p][idx];
		if(p==0){
			return false;
		}
	}
	return end[p];
}

查找一个字符串是否为其他字符串的前缀：

//判断当前字符是否为其他字符的前缀
bool prefix(string str){
	int p=1;
	for(int i=0;i<str.length();i++){
		int idx=str[i]-'a';
		p=trie[p][idx];
		if(p==0){
			return false;
		}
	}
	return true;
} 

遍历字符串：

//深度遍历字典树
void dfs(int p){
	for(int i=0;i<26;i++){
		if(trie[p][i]){
			cout<<char(i+'a');
			dfs(trie[p][i]);
		}
	}
	cout<<endl;
} 

统计一个字符串所有前缀单词的个数，只需要从根到叶子单词出现的个数，也可以判断一个单词是否为其他单词的前缀。

方法：只需要记录从根到叶子节点由多少个结束标记。

//判断一个字符串串有多少个前缀
int Scount(string st){
	int p=1;
	//记录前缀 
	int cnt=0;
	for(int i=0;i<st.length();i++){
		int idx=st[i]-'a';
		p=trie[p][idx]; 
		if(end[p]){
			cnt++; 
		}
	}
	return cnt;
}

主程序：

int main(){
	init();
	while(1){
		int flag;
		string st;
		string str;
		string fix;
        int cnt=0;
		menu();
		cout<<"请输入操作: ";
		cin>>flag;
		switch (flag){
			case 1:
				cout<<"请输入要输入的字符串数: "<<endl;
				cin>>n;
				while(n--){
					cout<<"请输入字符串: "<<endl;
					cin>>str;
					insert(str);
				}	
				break;
			case 2:
				cout<<"请输入要查找的字符串: "<<endl;
				cin>>st;
				if(search(st)){
					cout<<"查询成功"<<endl;
				}else{
					cout<<"查询失败!"<<endl;
				}
				break;
			case 3:
				cout<<"请输入要查找的字符串是否为其他字符的前缀: "<<endl;
				cin>>fix;
				if(prefix(fix)){
					cout<<"YES"<<endl; 
				}else{
					cout<<"NO"<<endl;
				}
				break;
			case 4:
				dfs(1);
				break;
			case 5:
				init();
				break;
            case 6:
				cout<<"请输入要统计的字符串前缀"<<endl;
				cin>>st;
				cnt=Scount(st);
				cout<<"该字符前缀数: "<<cnt<<endl;
				break;
			default:
				cout<<"结束操作!"<<endl; 
		}
		if(flag==7){
			break;
		}
	}
	return 0;
}

结果测试：

 

（2）使用链表实现

①定义数据结构

#include<iostream>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
struct Trie{
	int v;
	Trie*next[26];
	//构造函数初始化 
	Trie (){
		for(int i=0;i<26;i++){
			next[i]=NULL;
		}
		v=0;
	}
};
Trie *root;

②插入字典树中

void menu(){
	cout<<"----------------------------------"<<endl;
	cout<<"1.插入字符串到字典树"<<endl;
	cout<<"2.查找字符串是否存在"<<endl;
	cout<<"3.判断输入字符串是否为其他字符前缀"<<endl;
	cout<<"4.清空字典树"<<endl;
	cout<<"5.统计前缀树数"<<endl;
	cout<<"6.结束操作"<<endl;
	cout<<"----------------------------------"<<endl;
}
void insert(string s){
	int len=s.length();
	Trie *p=root;
	for(int i=0;i<len;i++){
		int id=s[i]-'a';
		if(p->next[id]==NULL){
			p->next[id]=new Trie();	
		}
		p=p->next[id];
        //使用p->v记录前缀数量 
		p->v++;
	}
	
	p->v=-1;
}

③搜索前缀，判断字符串是否存在

int search(string s){
	Trie *p=root;
	for(int i=0;i<s.length();i++){
		int id=s[i]-'a';
		p=p->next[id];
		if(p==NULL){//表示不存在该字符 
			return 0;
		}else if(p->v==-1&&(i<s.length()-1)){
		//表示该字符串中含有其他字符串作为该字符串的前缀
		//其实也就是说该字符串不存该字典树树，可用于判断是否包含前缀 
			return -1;
		}
	}
	//表示存在该字符串,但是不是其他字符串的前缀 
	if(p->v==-1){
		return 1;
	}else{
		//表示为其他字符串的前缀 
		return 2;
	}
}

④查找前缀数

int Find(string s){    //返回以字符串word为前缀的单词的数量
    Trie *p = root;
    for(int i=0;i<s.length();i++){    //在字典树找到该单词的结尾位置
    	int idx=s[i]-'a';
        if(p->next[idx]==NULL){
        	return 0;
		}
        p = p->next[idx];
    }
    return p->v;
}

⑤释放节点

void release(Trie*p){
	if(p==NULL){
		return ;
	}else{
		for(int j=0;j<26;j++){
			if(p->next[j]!=NULL){
				release(p->next[j]);
			}
		}
	}
	delete p;
}

⑥主函数

int main(){
	string s;
	root=new Trie();
	while(1){
		int flag=0;
		int n;
		int num;
		menu();
		cout<<"请输入操作: ";
		cin>>flag;
		switch(flag){
			case 1:
				cout<<"请输入插入字符串数: ";
				cin>>n;
				while(n--){
					cout<<"请输入插入的字符串: ";
					cin>>s;
					insert(s);
					cout<<"插入字典树中成功!"<<endl;
				}
				break;
			case 2:
				cout<<"请输入要字符串: ";
				cin>>s;
				flag=search(s);
				if(flag==1||flag==2){
					cout<<"存在字典树中"<<endl;
				}else{
					cout<<"不存在字典树中"<<endl;
				} 
				break;
			case 3:
				cout<<"请输入要字符串: ";
				cin>>s;
				flag=search(s);
				if(flag==2){
					cout<<"该字符串为其他字符串的前缀!"<<endl;
				}else{
					cout<<"该字符串不是其他字符串的前缀!"<<endl;
				} 
				break;
			case 4:
				release(root);
				root=new Trie();
				cout<<"清空成功!"<<endl;
				break;
			case 5:
				cout<<"请输入要统计的字符串前缀数: ";
				cin>>s;
				num=Find(s);
				cout<<"前缀数: "<<num<<endl;
				break;
			default:
				release(root);
				cout<<"结束操作!"<<endl; 
		} 
		if(flag==6){
			break;
		}
	}
	return 0;
}

 

 

 

3.字典树的应用

（1）字符串检索

事先将字符串存储到字典树Trie中，查找字符串，出现的频率和搜索引擎的热门查询

（2）前缀统计

统计一个字符串所有前缀单词的个数，只需要从根到叶子单词出现的个数，也可以判断一个单词是否为其他单词的前缀。

（3）最长公共前缀

两个字符串的最长公共前缀的长度就是它们所在节点最近公共祖先到根的长度。

（4）排序

利用字典树进行串排序，对字典树先序遍历，输出相应的字符串便是按字典排序的结果。

（5）作为其他数据结构与算法的辅助结构

如后缀树和AC自动机。