hihocoder#1014 Trie树提速字典查找

算法原题来自：hihocoder

你可以在我的github获取源码:https://github.com/Wtango/hihocoder

Trie树，Trie树的名字有很多，比如字典树，前缀树等等。Trie树可以应用与辞频统计、前缀统计等，其原理是利用公共前缀来减少查询的时间，减少无谓的查询以提高查询时间。

我们看一个Trie树例子：字典有app、apple、add三个单词

Trie树根节点不包含字符，除根节点外每一个节点都只包含一个字符；从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；每个节点的所有子节点包含的字符都不相同。每个节点所能容纳的子树应该为字典的字符宽度，即题目中为26个英文单词，则这个Trie树的度为26.

一、定义这个树的节点：

typedef struct TrieNode{
	struct TrieNode *childNode;
	char nodeChar;
	int count;
	uint8_t word_flag;	
}trie_node_t;

count用于统计经过这个节点的单词，我们在建立Trie树的时候就可以把这个字段初始化好，虽在这样可以大大提高我们统计单词前缀的速度。

二、添加节点

void add_trie_node(trie_node_t *root,const char *word,size_t len)
{
	if(len == 0)
		return;
	int k = word[0] - 'a';
	if(root->childNode[k].nodeChar == 0){
		init_node(&(root->childNode[k]),word[0],len == 1?1:0);
	}
	root->childNode[k].count += 1;
	add_trie_node(&(root->childNode[k]),++word,--len);
}

init_node()函数用来初始化一个节点，我们使用word[0] – ‘a’来计算当前字符应该放在当前节点的哪一个叶子。当添加单词经过一个节点时候就将count加1,表示有多少个单词经过这个节点，在统计前缀的时候就可以直接使用了。

三、查询

int search_tree(trie_node_t *root,const char *word,size_t len)
{
	if(len == 0)
		return 0;
	int k = word[0] - 'a';
	if(root->childNode[k].nodeChar == word[0]) {
		if(len == 1) {
				return root->childNode[k].count;
		}
		else {
			return search_tree(&(root->childNode[k]),++word,--len);
		}
	}
	return 0;
}

四、完整代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>

typedef struct TrieNode{
	struct TrieNode *childNode;
	char nodeChar;
	int count;
	uint8_t word_flag;	
}trie_node_t;

void init_node(trie_node_t *node,char nodeChar,uint8_t word_flag)
{
	node->childNode = (trie_node_t*)malloc(sizeof(trie_node_t) * 26);
	memset(node->childNode,0,sizeof(trie_node_t) * 26);
	node->nodeChar = nodeChar;
	node->count = 0;
	node->word_flag = word_flag;
}

void add_trie_node(trie_node_t *root,const char *word,size_t len)
{
	if(len == 0)
		return;
	int k = word[0] - 'a';
	if(root->childNode[k].nodeChar == 0){
		init_node(&(root->childNode[k]),word[0],len == 1?1:0);
	}
	root->childNode[k].count += 1;
	add_trie_node(&(root->childNode[k]),++word,--len);
}

int search_tree(trie_node_t *root,const char *word,size_t len)
{
	if(len == 0)
		return 0;
	int k = word[0] - 'a';
	if(root->childNode[k].nodeChar == word[0]) {
		if(len == 1) {
				return root->childNode[k].count;
		}
		else {
			return search_tree(&(root->childNode[k]),++word,--len);
		}
	}
	return 0;
}

int main(int argc,char *argv[])
{
	int times;
	char buf[11] = {0};
	trie_node_t root;
	init_node(&root,0,0);
	for(scanf("%d",&times);times != 0;times--) {
		scanf("%s",buf);
		add_trie_node(&root,buf,strlen(buf));
	}
	for(scanf("%d",&times);times != 0;times--) {
		scanf("%s",buf);
		int num = search_tree(&root,buf,strlen(buf));
		printf("%d\n",num);
	}
	return 0;
}

FEATURED TAGS

FRIENDS