也被称为词搜索树，Trie树，树形结构，是一种哈希树。典型的应用是用于统计、整理和保存大量的字符串（不限于字符串），所以他们经常用于文本词频统计的搜索引擎系统。
它的优点是通过使用字符串的公共前缀来节省存储空间，并最小化无意义字符串比较。查询效率高于哈希表。
的Trie树结构的优点是：
1）不限制子节点的数量；
2）自定义输入序列化突破了特定语言和应用程序的限制，成为一个通用的框架。
3）最大令牌序列长度的限制可以被限制；
4）根据固定阈值重复的字符串；
5）提供单个字符串频率搜索功能；
6）速度快，在两分钟内完成1998年1月人民日报（19056行）反复的字符串提取工作。
2。性能
它有3个基本属性：
1）根节点不包含字符，根节点和每个节点只包含一个字符。
2）从根节点到节点，路径上传递的字符连接到与该节点相对应的字符串。
3）每个节点的每个节点都包含不同的字符。
三.基本操作
它的基本操作是查找、插入和删除。当然，删除操作相对比较少见。我只是在这里实现了整个树的删除，一个单词的删除操作也非常简单。
4。实现方法
搜索字典项目的方法是：
（1）从根节点开始搜索。
（2）获取第一个字母来查找关键词，然后根据字母选择相应的子树，然后转到子树继续检索。
（3）在相应的子树，找得到关键词第二字母和相应的子树进行检索信件。
（4）迭代过程…
（5）在一个节点上，关键字的所有字母都被取出，并附加到节点上的信息被读取，即完成查找。
其他操作类似于处理。
5。Trie树原理-树的核心思想是以空间换时间。利用字符串的公共前缀来减少查询时间开销，提高效率。
6。代码实现
复制代码代码如下所示：
const int branchnum = 26； / /声明
int i；
结构trie_node
{
boolisstr； / /这里记录是否构成一个字符串。
trie_node *下{ branchnum }； / /指针每棵子树，下标0-25代表26个字符
trie_node（）：isstr（假）
{
memset（接下来，null，sizeof（下））；
}
}；
类树
{
公共：
Trie（）；
Voidinsert（const char *的话）；
boolsearch（char *的话）；
VoiddeleteTrie（trie_node *根）；
/ / voidprinttrie（trie_node *根）； / /新加
私人：
trie_node *根；
}；
Trie：：Trie（）
{
根=新trie_node（）；
}
特里：无效：插入（const char *的话）
{
trie_node *位置=根；
同时（*单词）
{
如果（地点->下{ *字'a' } = = null） / /建立
{
trie_node * TMP =新trie_node（）；
位置->下{ *字'a' } = TMP；
}
位置=位置->下{ *字'a' }； / /插入的每一步，一个新的字符串指针下移后的等效。
词+；
}
位置- > isstr = true； / /尾，标记字符串
}
布尔检索：：搜索（char *的话）
{
trie_node *位置=根；
同时（*位置）
{
位置=位置->下{ *字'a' }；
词+；
}
返回（位置！=零位置-> isstr）；
}
空树：：deletetrie（trie_node *根）
{
为（i = 0；i < branchnum；i++）
{
如果（根>下一个{ }！= null）
{
DeleteTrie（根->下{我}）；
}
}
Deleteroot；
}
空（主）/简单测试
{
Trie树T；
T.insert（）；
T.insert（抛弃）；
char放弃；
T.insert（C）；
T.insert（羞）；
如果（t.search（羞））
{
printf（真；已插入
}
}
有时，我们会遇到字符串的排序。如果我们使用一些经典的排序算法，时间复杂度是O（N * LGN），但如果我们用Trie树，时间复杂度为O（n）。
Trie树也叫名字的树。它可以从字面意义上理解。这棵树的结构像一本英语词典。相邻词具有相同的前缀，时间复杂度较低，因为它们使用时间与空间交换的策略。
下面是一个对Trie树的排序字符串（这里我们假定字符串是小写），每个节点有26个分支，每个分支代表一个字母的节点存储在一个字符串从根节点到节点上的字符的路径。
将每个字符串Trie树，达到特定的目的节点，此节点上的马克，如插入基地
在那之后，树的遍历，通过前序，和字符串从小到大的顺序可以得到。
实现代码如下：（++，vc++编译和通过）：
复制代码代码如下所示：
#包括
#包括
使用名称空间；
#定义数字26
类节点
{
公共：
int计数；字符串的记录数
结* char_arr {民}； / /分
char * current_str； / /字符串中的所有字母记录到这里的路径组成的
Node（）；
}；
类树
{
公共：
节点*根；
Trie（）；
空插入（char * STR）；
空输出（节点*节点，char * STR，int计数）；
}；
过程没有考虑删除动态内存。
主（）
{
char =新的char { 12 }；
STR { 0 } =zbdfasd ；
STR { 1 } =zbcfd ；
STR { 2 } =zbcdfdasfasf ；
STR { 3 } =abcdaf ；
STR { 4 } =defdasfa ；
STR { 5 } =fedfasfd ；
STR { 6 } =dfdfsa ；
STR { 7 } =dadfd ；
STR { 8 } =dfdfasf ；
STR { 9 } =abcfdfa ；
STR { 10 } =fbcdfd ；
STR { 11 } =abcdaf ；
/ /一个Trie树
特里*树=新的线索（）；
对于（int = i 0；i < 12；i + +）
特里->插入（STR {我}）；
int计数= 0；
Trie树（trie ->输出->根，STR，计数）；
对于（int = i 0；i < 12；i + +）
cout << STR {我} << endl；
返回0；
}
节点：：Node（）
{
计数= 0；
对于（int = i 0；i <数字；i + +）
我char_arr { } = null；
current_str =新字符{ 100 }；
current_str { 0 } =0；
}
Trie：：Trie（）
{
根=新节点（）；
}
特里：无效：插入（char * str）
{
int = i 0；
节点*父=根；
/ /插入序列{我}到trie树
当（{ } }）！=0）
{
如果有分支，其中包含新的分支，这是新的分支。
如果（母-> char_arr { str {我} - 'a' } = = null）
{
母-> char_arr { str {我} - 'a' } =新的节点（）；
父节点中的字符串添加到字符串中的当前节点。
Strcat（母-> char_arr { str {我} - 'a' } -> current_str，母-> current_str）；
焦str_tmp { 2 }；
str_tmp { 0 } = {我} STR；
str_tmp { 1 } =0；
将添加到字符串中的当前节点。
Strcat（母-> char_arr { str {我} - 'a' } -> current_str，str_tmp）；
父母=父母-> char_arr { str {我} - 'a' }；
}
其他的
{
父母=父母-> char_arr { str {我} - 'a' }；
}
++；
}
父> >计数+；
}
/ /由序
空树：：输出（节点的节点，char * str，int数）
{
如果（节点）！= null）
{
如果（节点>计数！= 0）
{
对于（int = i 0；i计数；i + +）
STR {计数+ } =节点-> current_str；
}
对于（int = i 0；i <数字；i + +）
{
输出（节点-> char_arr {我}，STR，计数）；
}
}
}
