一、Trie树简介
Trie树，是一种树形结构，是一种hash树的变种，Trie树的名字有很多，比如字典树，前缀树等等，典型应用是用于统计，排序和保存大量的字符串，经常被搜索引擎用于文本词频统计。特点利用字符串的公共前缀来减少查询时间，最大限度减少字符串匹配的时间，效率比哈希表高。
字典树（Trie）是保存一些字符串->值的对应关系。基本上和 HashMap 功能相同，都是 key-value 映射，只不过 Trie 的 key 只能是字符串。
Trie树的强大之处就在于它的时间复杂度。它的插入和查询时间复杂度都为 O(k) ，其中 k 为 key 的长度，与 Trie 中保存了多少个元素无关。Hash 表号称是 O(1) 的，但在计算 hash 的时候就肯定会是 O(k)；Trie 的缺点是空间消耗很高。
至于Trie树的实现，可以静态实现，也可以用指针动态实现。
二、Trie树基本性质
（1）根节点不包含字符，除根节点外，每个节点只包含一个字符
（2）从根节点到某一个节点，路径上进过的节点连接起来，为该节点对应的字符串
（3）每个节点的所有子节点包含的字符串不同
（4）如果字符的种数为n，则每个节点的出度为n，这也是空间换时间的体现，浪费了很多空间
（5）插入查找的复杂度为Ο(n)，n为字符串长度
基本思想（为是便于理解，令字符为26个小写的英文字母）
1、插入过程
对于一个单词，从根开始，沿着单词的各个字母所对应树中的节点分支往下走，直到单词遍历完将最后的节点标记为红色，表示该单词已插入Trie树
2、查询过程
从根开始按照字母的顺序向下遍历Trie树，一旦发现某个节点标记不存在或者单词遍历完而最后的节点未标记红色，则表示该单词不存在。若最后的节点标记为红色，则便是该单词存在。
3、删除过程
一般是很少删除树上一个单独节点，因此一般只考虑删除整棵树，用递归可以很容易实现。
三、字典树的数据结构
利用串构建一个字典树，这个字典树保存串的公共前缀信息，因此可以降低查询操作的复杂度下面以英文单词构建的字典树为例，这棵Trie树中每个结点包括26个孩子结点，因为总共有26个英文字母(假设单词都是小写字母组成)。
Trie树的结点信息的结构体
typedef struct TrieNode
{
int count ; //计单词前缀出现的次数
char isStr; // 标记该结点处是否构成单词
struct TrieNode* next[26];
}TrieNode;
如给出字符串"abc","ab","bd","dda"，根据该字符串序列构建一棵Trie树。则构建的树如下
:
#include<stdio.h>
#include<malloc.h>
#include<string.h>
typedef struct TrieNode
{
int count ; //计单词前缀出现的次数
char isStr; // 标记该结点处是否构成单词
struct TrieNode* next[26];
}TrieNode;
TrieNode* createTrieNode()
{
TrieNode *node = (TrieNode*)malloc(sizeof(TrieNode));
node->count=0;
node->isStr=0;
int i;
for(i=0;i<26;i++)
node->next[i]=NULL;
return node;
}
void Trie_Insert(TrieNode* T,char *str)
{
TrieNode* node = T,*temp;
char *p=str;
int id=0;
printf("Trie_Insert:");
while(*p)
{
id=(*p)-'a';
printf("%c",*p);
if(node->next[id]==NULL)
node->next[id]=createTrieNode();
node=node->next[id];
node->count++;
++p;
}
printf("\n");
node->isStr=1;
}
int Trie_Search(TrieNode* T,char * str)
{
TrieNode* node = T;
char *p = str;
int id;
printf("Trie_Search:");
while(*p)
{
id=(*p)-'a';
printf("%c",*p);
if(node->next[id]==NULL)
return 0;
node=node->next[id];
p++;
}
return node->count;
}
void del(TrieNode *root)
{
for(int i=0;i<10;i++)
if(root->next[i]) del(root->next[i]);
free(root);
}
int main(int argc,char **argv)
{
TrieNode* root=createTrieNode();
char str[12];
char flag = 0;
while(gets(str))
{
if(flag)
printf("\n%d\n",Trie_Search(root,str));
else
{
if(strlen(str) != 0)
Trie_Insert(root,str);
else
flag = 1;
}
}
return 0;
}
| 
转播
