字典树实现

简介

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
--------------------百度百科

图示

将to,tea,ted,ten,a,in,inn插入字典树中,单词结束的位置用红色标记

代码

#include 
#include 

using namespace std;

const int maxn = 26; // 第一层最多又26个节点 

struct treenode{ // 字典树的结构 
	bool isWord; // 判断是否有改单词（图中的红色标记）
	struct treenode *next[maxn];  
};

treenode *createnode(){ // 创建一个新的节点 
	treenode *p = new treenode;
	p->isWord = false; // 初始化节点 
	for(int i = 0; i < maxn; i++)
		p->next[i] = NULL;
	return p;
}

void insertnode(treenode **root, string str){ // 将单词中的字母插入字典树中 
	treenode *p;
	if(*root == NULL){ // 如果根节点值为空(NULL)新建一个节点 
		p = createnode();
		*root = p;
	}
	else  
		p = *root;
	for(int i = 0; i < str.length(); i++){
		int k = str[i] - 'a';
		if(p->next[k] == NULL) // 没有改字母节点就插入一个节点 
			p->next[k] = createnode();
		p = p->next[k]; // 更新p的值 
	}
	p->isWord = true; // 全部字母插入完成后为一个单词 
}

bool searchnode(treenode **root, string str){ // 查找单词 
	treenode *p;
	if(*root == NULL) // 如果根节点为空(NULL)直接返回false 
		return false;
	p = *root;
	for(int i = 0; i < str.length(); i++){
		int k = str[i] - 'a';
		if(p->next[k] == NULL) // 如果改字母不在字典树中返回false 
			return false;
		p = p->next[k]; // 更新p的值 
	}
	if(p->isWord) // 如果改单词存在返回true（图中的红色标记）
		return true;
	return false;
}

int main(){
	treenode *root = NULL; // 根节点赋值为空(NULL) 
	string str, src;
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){ // 循环插入单词 
		cin >> str;
		insertnode(&root, str); 
	}
	while(1){ // 查找 
		cin >> src;
		if(searchnode(&root, src))
			cout << "YES" << endl;
		else
			cout << "NO" << endl;		
	}	
}