字典树概述

字典树概述2015-09-10字典树简介

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

字典树有3个基本性质：

1、根节点不包含字符，其余的每个节点都包含一个字符；

2、从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；

3、每个节点的所有子节点包含的字符都不相同。

字典树的结构一般如下图所示：

以字符串为例，我们可以将其存储结构写成如下形式：

#define MAX 26//字符集的大小/* 字典树的存储结构 */typedef struct Node{struct Node *next[MAX]; //每个节点下面可能有MAX个字符int count;//以从根节点到当前节点的字符串为公共前缀的字符串数目}TrieNode,*TrieTree;

这里，因为我们用的字符集为26个小写字母，因此MAX为26。可以将此数据存储结构与上面的存储图例相比较，以加深理解。这里很容易看出，字典树是典型的用空间换时间，存储空间极大，这在海量字符串时很适用。

字典树有如下2个优点：

1.利用字符串的公共前缀来节约存储空间。

2.最大限度地减少无谓的字符串比较，查询效率比较高。

字典树的应用

字典树的应用很广泛，下面是摘自百度百科的3个应用介绍：

1、在串快速检错中的应用

字典树的应用很广泛，下面是摘自百度百科的3个应用简介：

1、字典树在串的快速检索中的应用。

给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。在这道题中，我们可以用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。