前言
最近无聊，用70%C和30%C++写了个Trie树的源程序，源码可在CodeBlocks、VC++等上面运行
Trie树
含义：
Trie树，即字典树，又称单词查找树，是一种树形结构，是一种哈希树的变种。
典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以
经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀
来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
三个基本性质：
1.根节点不包含字符，除根节点外每一个节点都只包含一个字符；
2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
3.每个节点的所有子节点包含的字符都不相同。
简而言之，Trie树就是根据公共前缀来存储元素的多叉树吧（下图转载）
一．题目要求
1)初始化
2)插入元素
3)删除元素
4)查找元素
5)Trie树的应用
二．数据结构体
typedef struct TrieNode
{
struct TrieNode
*next
[Max
];
int if_end
;
int node_count
;
char word
;
} TrieNode
, *TrieNodePtr
, *TrieSTPtr
;
三．主要函数
1. 插入函数 void Trie_insert(TrieNodePtr root,char *word)
包含的参数：Trie数的根节点root ， 插入元素的字符串地址word。
返回值：（无返回值）。
2.查找函数 int searchTrie(TrieNodePtr root,char *word)
包含的参数：Trie数的根节点root ， 查询元素的字符串地址word。
返回值：（int类型）如果存在就返回1，不存在就返回0。
3.删除函数
TrieNodePtr Trie_delect(TrieNodePtr root,char *word,int locate)
包含的参数：Trie数的某节点root，被删除元素的字符串地址word和该元素
的第locate个字符。
返回值：（结构图指针类型）返回值是否NULL决定了递归时要进行的操作
四．函数块及其解析
1.插入函数
trie树是一棵多叉树，它的插入要遵循相邻两个结点存储的字符不能相同这
一规则，并且新建结点要用calloc使其结点内容初始化为空，若是已存在该
结点，它的父母结点的子节点数要加1，若是已到达插入元素的最后一个
结点，需要把最后一个结点的元素结束标志改为TRUE。
void Trie_insert(TrieNodePtr root
, char *word
){
int i
= 0;
TrieSTPtr tmp
= root
;
while (*(word
+ i
) != '\0') {
int Ascll
=*(word
+ i
);
if (tmp
->next
[abs(Ascll
)] == NULL)
{
tmp
->next
[abs(Ascll
)] = (TrieNode
*)calloc(1, sizeof(TrieNode
));
tmp
->next
[abs(Ascll
)]->word
=*(word
+i
);
tmp
->node_count
++;
}
tmp
= tmp
->next
[abs(Ascll
)];
i
++;
}
tmp
->if_end
= TRUE
;
}
2.查找函数
查找函数在判断条件上类似于插入函数，如果元素的某个字符在Trie树
中不存在对应结点，说明不存在该元素，直接结束查找。如果所有
字符均存在且最后一个字符结点的元素结束标志是TRUE，元素存在。
int searchTrie(TrieNodePtr root
,char *word
) {
if(root
==NULL) {
printf("该Trie树未初始化！\n");
return 0 ;
}
TrieNodePtr tmp
=root
;
int i
=0;
while(word
[i
]!='\0') {
int Ascll
=abs(word
[i
]);
if(tmp
->next
[Ascll
]==NULL){printf("没有该元素(或已删除)!\n");return 0 ;}
else tmp
=tmp
->next
[Ascll
];
i
++;
}
if (tmp
->if_end
== TRUE
){
printf("存在该元素！\n");
return 1;
}
else {
printf("不存在该元素！(或已删除)\n");
return 0;
}
}
3.删除函数
删除函数是本Trie树最复杂的一个函数，要考虑多种情况，相关的解析我
在代码中也有更详细的记载。
（1）首先我们需要先用递归的方法找到被删除元素的最后一个字符结点，
判断该结点后是否还有子节点，若没有，就说明这个字符结点仅属于
被删元素，因为同一条路扫描下来的最后一个字符结点不可能同时属
于两个不同的元素，并且Trie树的路径是不会交叉的，只会有分支，
意味着其它路径的元素是不会连接到该结点的，所以这是这个元素结
点是可以删除的，这是时需要return一个NULL来进行后续的删除。若
是该结点还有子节点，说明被删元素的最后一个字符结点是其它元素
的子节点，也说明这个被删元素是其它元素的一个字串，这时需要返
回一个非空的指针来阻止回溯时删除结点的操作，并且将该结点的元
素结束符号取反。
（2）在回溯中，最后一个结点返回的指针是否空决定了前面所有字符结
点是否可以被删除，若返回NULL，前面所有结点不能被删除。
（3）否则便进入另一种情况：先删除被删元素的最后一个结点，再判断
被删元素倒数第二个结点是否符合删除的条件。（判断的依据类似步
骤 （1））。
TrieNodePtr
Trie_delect(TrieNodePtr root
,char *word
,int locate
) {
if(*(word
+locate
)!='\0') {
TrieNodePtr tmp
;
int Ascll
=*(word
+locate
);
tmp
=root
->next
[abs(Ascll
)];
tmp
=Trie_delect(tmp
,word
,locate
+1);
if(tmp
==NULL) {
delete( root
->next
[abs(Ascll
)]);
root
->next
[abs(Ascll
)]=NULL;
if(root
->node_count
!=0) {
root
->node_count
--;
}
if(root
->if_end
==TRUE
) {
return root
;
}
else if (root
->if_end
==FALSE
&&root
->node_count
==0) {
return NULL;
}
}
else {
return root
;
}
}
else {
if(root
->node_count
==0) {
root
=NULL;
}
else {
root
->if_end
=FALSE
;
}
return root
;
}
}
五．调试分析
1.用户界面
2.测试数据
(1)Trie树初始化
(2)插入5个相似元素（相似元素只为检验的可靠性） Sujunzhong Su jun zhong Su zong Su Suxjunzhong
(3)删除元素
删除元素之前和之后都会进行一次查找被删元素操作
（4）查找元素
六. Trie树的应用
（1）字符串检索 （2）字符串最长公共前缀 （3）排序 （4） 作为其他数据结构和算法的辅助结构 （5）词频统计 （6）字符串搜索的前缀匹配（本人认为最常见也最实用）
七．源码附录
#include <iostream>
#include <stdio.h>
#include <malloc.h>
#include <memory.h>
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
#define NULL 0
#define Max 260
#define TRUE 1
#define FALSE 0
using namespace std
;
typedef struct TrieNode
{
struct TrieNode
*next
[Max
];
int if_end
;
int node_count
;
char word
;
} TrieNode
, *TrieNodePtr
, *TrieSTPtr
;
void Trie_insert(TrieNodePtr root
,char *word
);
int searchTrie(TrieNodePtr root
,char *word
);
TrieNodePtr
Trie_delect(TrieNodePtr root
,char *word
,int locate
);
void interface(){
TrieSTPtr root
;
int choice
;
while(1)
{
printf("\t\t\t\t\t~~~~~~~~~~~~~~~~~~~\n");
printf("\t\t\t\t\t||欢迎来到Trie树||\n");
printf("\t\t\t\t\t===================\n");
printf("\t\t\t\t\t||1.Trie树初始化 |\n ");
printf("\t\t\t\t\t||2.插入元素 |\n ");
printf("\t\t\t\t\t||3.删除元素 |\n ");
printf("\t\t\t\t\t||4.查找元素 |\n");
printf("\t\t\t\t\t||0.退出程序 |\n ");
printf("\t\t\t\t\t===================\n");
printf("请输入您的操作：");
scanf("%d",&choice
);
while((getchar())!='\n');
switch (choice
)
{
case 1: {root
= (TrieSTPtr
)calloc(1, sizeof(TrieSTPtr
));
if (root
==NULL) printf("初始化失败！\n");
else printf("初始化成功！\n");
break;}
case 2: {
printf("请输入要录入的元素个数：");
int num
;
scanf("%d",&num
);
while((getchar())!='\n');
char word
[26];
for(int i
=1;i
<=num
;i
++){
printf("请输入第%d个元素：",i
);
gets(word
);
Trie_insert(root
,word
);
printf("第%d个元素(%s)录入成功！\n",i
,word
);
}printf("全部录入完毕！\n\n");
break;
}
case 3: {
printf("请输入你要删除的元素：");
char word
[26];
gets(word
);
if (root
==NULL){printf("该树未初始化!\n");break;}
printf("删前一查：");
int d
=searchTrie(root
,word
);
if(d
==0) break;
Trie_delect(root
,word
,0);
printf("为您查询结果：");
searchTrie(root
,word
);
break;
}
case 4: {
char word
[26];
printf("请输入你要查找的元素：");
gets(word
);
searchTrie(root
,word
);
printf("\n查找完毕(~_~)\n\n");
break;
}
case 0: printf("欢迎再次使用程序\n");
return ;
default : printf("不存在功能，请检查输入\n\n");
break;
}
}
}
void Trie_insert(TrieNodePtr root
, char *word
){
int i
= 0;
TrieSTPtr tmp
= root
;
while (*(word
+ i
) != '\0') {
int Ascll
=*(word
+ i
);
if (tmp
->next
[abs(Ascll
)] == NULL)
{
tmp
->next
[abs(Ascll
)] = (TrieNode
*)calloc(1, sizeof(TrieNode
));
tmp
->next
[abs(Ascll
)]->word
=*(word
+i
);
tmp
->node_count
++;
}
tmp
= tmp
->next
[abs(Ascll
)];
i
++;
}
tmp
->if_end
= TRUE
;
}
int searchTrie(TrieNodePtr root
,char *word
) {
if(root
==NULL) {
printf("该Trie树未初始化！\n");
return 0 ;
}
TrieNodePtr tmp
=root
;
int i
=0;
while(word
[i
]!='\0') {
int Ascll
=abs(word
[i
]);
if(tmp
->next
[Ascll
]==NULL){printf("没有该元素(或已删除)!\n");return 0 ;}
else tmp
=tmp
->next
[Ascll
];
i
++;
}
if (tmp
->if_end
== TRUE
){
printf("存在该元素！\n");
return 1;
}
else {
printf("不存在该元素！(或已删除)\n");
return 0;
}
}
TrieNodePtr
Trie_delect(TrieNodePtr root
,char *word
,int locate
) {
if(*(word
+locate
)!='\0') {
TrieNodePtr tmp
;
int Ascll
=*(word
+locate
);
tmp
=root
->next
[abs(Ascll
)];
tmp
=Trie_delect(tmp
,word
,locate
+1);
if(tmp
==NULL) {
delete( root
->next
[abs(Ascll
)]);
root
->next
[abs(Ascll
)]=NULL;
if(root
->node_count
!=0) {
root
->node_count
--;
}
if(root
->if_end
==TRUE
) {
return root
;
}
else if (root
->if_end
==FALSE
&&root
->node_count
==0) {
return NULL;
}
}
else {
return root
;
}
}
else {
if(root
->node_count
==0) {
root
=NULL;
}
else {
root
->if_end
=FALSE
;
}
return root
;
}
}
int main()
{
interface();
return 0;
}
本期对Trie树的分享到此结束，不喜勿喷，下期再见
