Trie -字典树

基本原理

字典树,又称Trie树,是一种树形结构.典型应用就是用于统计,排序和保存大量的字符串(不仅限于字符串).

主要思想是利用字符串的公共前缀来节约存储空间

上图就是一颗字典树,“从根节点到任意一个红色节点的路径上的字母组成一个单词”.

字典树主要包含两种操作:

• 插入
• 查找

初步学习需要重点掌握插入和查找操作

代码模板

struct trie{
	trie* next[26];
	int num;
	trie(){
		for(int i=0;i<26;i++){
			next[i]=NULL;
		}
		num=0;
	}

}root;
void insert(char *s){
	trie *p=&root;
	for(int i=0;s[i]!='\0';i++){
		if(p->next[s[i]-'a']==NULL){
			p->next[s[i]-'a']=new trie;
		}
		p=p->next[s[i]-'a'];
		p->num++;
	}
}

int find(){
	trie *p=&root;
	for(int i=0;s[i]!='\0';i++){
		if(p->next[s[i]-'a']==NULL)
			return 0;
		else 
			p=p->next[s[i]-'a'];
	}
	return p->num;
}