前缀树（字典树）Trie Tree

本文转载于https://blog.csdn.net/Jane_96/article/details/95900447

前缀树

含义

Trie树，即前缀树，又称单词查找树或字典树，是一种树形结构。该树典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

应用

题目：给你100000个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，求第一次出现在第几个位置。
在Trie树适用的状态下，很多情况同样可以使用hash树。但是Trie树用途更加的广泛，比如给一个字符串，要寻找有多少单词是以该字符串为前缀的问题。

代码解析

Trie树节点结构

const int branchNum = 26; // 26叉树
struct TrieNode {
	bool isStr; // 标识是否是一个完整的字符串
	TrieNode* next[branchNum]; // 每个字符的Trie树分支可能存在26个分支
};

Trie树插入操作

/*前缀树建立的过程*/
void Insert(TrieNode* root,const char* word)
{
	TrieNode* location=root;
	while(*word)
	{
		//若节点的子节点为空，创建一个子节点
		if(location->next[*word-'a']==NULL)
		{
			TrieNode* newNode=new TrieNode();
			newNode->isStr=false;
			memset(newNode->next,NULL,sizeof(newNode->next) );
			location->next[*word-'a']=newNode;
		}
		location=location->next[*word-'a']; //location指向字符串在前缀树中的位置
		word++; //当前字符在字符串中的位置
	}
	//字符串已经全部添加到前缀树中，
	//标识前缀树到该节点为止为完整字符串
	location->isStr=true;
}	

Trie树查找操作

/**
 * 遍历前缀树，查看指定字符串是否存在
 */
bool Search(TriNode* root , const char* word){
 	TrieNode* location = root;
 	while(*word && location != NULL){
  		location = location->next[*word - 'a'];
  		word++;
 	}
 	return (location != NULL && location->isStr);
}

Trie树删除操作

/**
 * 删除前缀树
 */
void Delete(TrieNode* location){	
	for(int i = 0; i < branchNum; i++){
  		if(location->next[i] != NULL){
   			Delete(location->next[i]);
  		}
 	}
 	delete location;
}

测试

#include<iostream>
#include<cstring>
using namespace std;
const int BRANCHNUM = 26;
struct TrieNode {
	TrieNode *next[BRANCHNUM];
	bool isStr；
}

void Insert(TrieNode *root , const char *word){	
	TrieNode *location = root;
 	while(*word){
  		if(location->next[*word - 'a'] == NULL){
   			TrieNode *newNode = new TrieNode();
   			newNode->isStr = false;
   			memset(newNode->next , NULL , sizeof(newNode->next));
   			location->next[*word - 'a'] = newNode;
  		}
  		location = location->next[*word - 'a'];
  		word++;
	 }
 	location->isStr = true; 
}

bool Search(TrieNode *root , const char *word){
	TrieNode *location = root;
	while(*word && location != NULL){
		location = location->next[*word - 'a'];
		word++;
	}
	return (location && location->isStr);
}

void Delete(TrieNode *root){
	for(int i = 0;i < BRANCHNUM;i++){
		if(root->next[i]){
			Delete(root->next[i]);
		}
	}	
	delete root;
}

int main(){
	TrieNode *root = new TrieNode();
	root->isStr = false;
	memset(root->next , NULL , sizeof(root->next)); 
	Insert(root , "apple");
	Insert(root , "banana");
	Insert(root , "car");
	cout << "是否包含单词bana ： " << Search(root , "bana") << endl;
	cout << "是否包含单词car ： " << Search(root , "car") << endl;
	
	return 0;
}

拓展

上述 Trie树结构中，每个node节点只含有两部分信息————节点是否是字符串的终点和节点的子节点。现在对节点添加两个其他信息————走过该节点的单词数(pathNum)和以该节点结尾的单词数(endNum);
作用：查询字符串集中某个字符串出现的次数或者以某个字符串为前缀的单词数

节点结构

const int branchNum = 26; // 26叉树
struct TrieNode {
	bool isStr; // 标识是否是一个完整的字符串
	TrieNode *next[branchNum]; // 每个字符的Trie树分支可能存在26个分支
    	int pathNum; // 走过该节点的单词数 , 即以所给字符串为前缀的单词数
    	int endNum; // 以该节点结尾的单词数 , 找相同单词的个数  
};

代码

#include<iostream>
#include<cstring>
using namespace std;

const int BRANCHNUM = 26;

struct TrieNode {
	bool isStr; // 标识是否是一个完整的字符串
	TrieNode *next[BRANCHNUM]; // 每个字符的Trie树分支可能存在26个分支
    int pathNum; // 走过该节点的单词数 , 即以所给字符串为前缀的单词数
    int endNum; // 以该节点结尾的单词数 , 找相同单词的个数  
};

void Insert(TrieNode *root , const char *word){
	TrieNode *location = root;
	while(*word){
		if(location->next[*word - 'a'] == NULL){
			TrieNode *newNode = new TrieNode();
			newNode->isStr = false;
			newNode->pathNum = 1;
			newNode->endNum = 0;
			memset(newNode->next , NULL , sizeof(newNode->next));
			location->next[*word - 'a'] = newNode;
		}else{
			location->next[*word - 'a']->pathNum = location->next[*word - 'a']->pathNum + 1; 
		} 
		
		location = location->next[*word - 'a'];
		
		word++;
	}
	location->isStr = true; 
	location->endNum += 1;
}

bool Search(TrieNode *root , const char *word){
	TrieNode *location = root;
	while(*word && location != NULL){
		location = location->next[*word - 'a'];
		word++;
	}
	return (location && location->isStr);
}

int SearchPathNum(TrieNode *root , const char *word){
	TrieNode *location = root;
	while(*word && location != NULL){ 
		location = location->next[*word - 'a'];
		word++;
		
	}
	if(location){
 		return location->pathNum;
 	}
 	return 0; 
}

int SearchEndNum(TrieNode *root , const char *word){
	TrieNode *location = root;
	while(*word && location != NULL){
		location = location->next[*word - 'a'];
		word++;
	}
	if(location){
 		return location->endNum;
 	}
 	return 0; 
}

void Delete(TrieNode *root){
	for(int i = 0;i < BRANCHNUM;i++){
		if(root->next[i]){
			Delete(root->next[i]);
		}
	}	
	delete root;
}

int main(){
	TrieNode *root = new TrieNode();
	root->isStr = false;
	root->pathNum = 1;
	root->endNum = 0;
	memset(root->next , NULL , sizeof(root->next)); 
	
	Insert(root , "apple");
	Insert(root , "ban");
	Insert(root , "bana");
	Insert(root , "banan");
	Insert(root , "banana");
	Insert(root , "car");
	Insert(root , "apple");
	Insert(root , "apple");
	
	cout << "以字符串ba为前缀的单词数有 ： " << SearchPathNum(root , "ba") << "个" << endl;
	cout << "字符集中apple单词出现过 ： " << SearchEndNum(root , "apple") << "次" << endl;
	
	return 0;
}