Trie树的插入、查询、删除和部分应用
Trie树的插入、查询、删除和部分应用
Trie树，又称字典树或前缀树，是一种用于快速检索的多叉树结构。它在处理大量字符串数据时表现出色，广泛应用于搜索引擎、自动补全系统等领域。本文将详细介绍Trie树的基本概念、实现方法及其在单词查询和词频统计等场景中的应用。
Trie树基本知识
Trie树，又称字典树、前缀树，是一种树形结构，是哈希树的变种，是一种用于快速检索的多叉树结构。
典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
它长这个样子：
结构体的构成
struct trieNode
{
char val;///指的是当前指针直接指向的字母
trieNode** son;///类似为指向trieNode类型的数组，其中下标1-25对应'a'-'z'
int cnt;///表示字符结束的标志，为0则未结束，其他同时也指该单词出现的次数
trieNode(char c)///初始化
{
val=c;
son=new trieNode*[N];
for(int i=0; i<N; i++)
{
son[i]=NULL;
}
cnt=0;
}
};
Trie树的插入
简单思路便是遇到一个新的字符串便遍历该字符串，遇到每个合适的字符就直接插入，并且令p指向下一个对应的位置。
注：目前我的代码只包括小写字母，不包括大写字母和其他的字符，所以要将大写字母转化为小写字母，同时不能插入其他的字符。
void inserts(char s[])
{
trieNode *p=root;
int i;
int c;
for(i=0; i<strlen(s); i++)
{
if(s[i]>='A' && s[i]<='Z') ///将大写转化为小写
c=s[i]-'A';
else if(s[i]>='a' && s[i]<='z')
c=s[i]-'a';
else
continue;
if(!p->son[c])
p->son[c]=new trieNode(c);
p=p->son[c];
p->val=c+'a';
}
p->cnt++;
}
Trie树的查询
此处查询与插入类似，返回该单词出现的次数。
int query(char s[])
{
trieNode *p=root;
int i;
for(i=0; i<strlen(s); i++)
{
int c=s[i]-'a';
if(!p->son[c]) return 0;
p=p->son[c];
}
return p->cnt;
}
Trie树的删除
删除Trie树的一个单词貌似是有很多方法的，我这里是在单词存在的情况下让出现的次数（对应cnt）减一，如果要将全部对应该单词删掉，让cnt=0即可。
int Delete(char s[])
{
trieNode *p=root;
if(query(s)==0)
{
printf("不存在该单词！\n");
return 0;
}
for(int i=0; i<strlen(s); i++)
{
int c=s[i]-'a';
if(!p->son[c]) return 0;
p=p->son[c];
}
p->cnt--;
return 1;
}
Trie树的应用
因为插入文本下面经常用到，所以就把插入文本单独拿出来。
插入文本
简单思路就是对写入的文本进行分割，分割成功后便直接利用inserts()插入该单词，并且把所有出现的单词存在一个结构体容器中，方便之后的遍历
///写入文本，插入相关单词
void Text()
{
//1-以单个字符来输入文本，以空格来分割，将前面已经出现的单词插入root中
//以#为结束标志
char words[50];
int i=0,j=0;
printf("请输入文本(输入#代表结束):\n");
///插入词语
char ch='+';
int Flags=1;
while(1)
{
scanf("%c",&ch);
if((ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z'))
{
words[i++]=ch;
Flags=1;
}
else if(Flags==1)
{
words[i++]='\0';
Flags=0;
printf("words是:%s\n",words);
///printf("length是：%d\n",strlen(words));
inserts(words);
///printf("过了insert\n");
i=0;
}
if(ch=='#') break;
}
///删除CONTAINER中重复的单词
}
应用1：检索单词是否出现在文本中
主要利用上面已经写过的query()函数
void accour()
{
root=new trieNode(' ');///建立根节点
Text();
//输入单个单词询问是否有出现,直接用query
while(1)
{
system("cls");
printf("请输入要查询的单词，输入0表示结束");
char s[50];
cin>>s;
if(strcmp(s,"0")==0)
break;
if(query(s)==0)
printf("不存在");
else
printf("存在，且出现了%d次\n",query(s));
system("pause");
}
}
应用2：统计所有出现过的单词词频
因为我本人对DFS技术还是不够好，特别是当前还需要处理字符串前缀相同的问题，所以捣鼓了好久，终于得到下面的代码。我是主要利用栈来存储已经度过的节点，利用DEVIDE数组存储经过的字符，再利用Devide的加减（当前节点不是栈头的儿子则要一直减1），从而表示字符串长度，最终成功输出
void DFS(trieNode *p)
{
int i;
trieNode *top=STA.top();
///这里的Devide可能不太准确
while(STA.top()->son[p->val-'a']!=p && !STA.empty())
{
Devide--;
STA.pop();
// printf("不相等\n");
}
if(p!=root)
DEVIDE[Devide++]=p->val;
// printf("Devide是：%d\n",Devide);
// if(STA.top()->son[p->val-'a']==p)
// printf("相等\n");
if(p->cnt!=0)
{
DEVIDE[Devide]='\0';
printf("%s：",DEVIDE);
printf("%d\n",query(DEVIDE));
}
STA.push(p);
// printf("测试%c\n",p->val);
extra=p;
for(i=0;i<N;i++)
{
if(p->son[i]!=NULL && p!=NULL)
{
DFS(p->son[i]);
}
}
}
void Traves()
{
root=new trieNode(' ');///建立根节点
Text();
printf("下面是所有单词以及出现的次数：\n");
// printf("what?\n");
extra=root;
Devide=0;
STA.push(root);
DFS(root);
}
因为一开始我想写出DFS方法的代码时出现了太多错误，所以也想用过不用DFS的，大概方法是这样的：
可以创建一个结构体，存下所有的单词和出现的频率，最终直接输出就行.这个方法思路比DFS简单，但是说实话耗费的时间和空间就要大了不少，没有达到原先存储为trie树所带来的优势，所以我最后还是努力写写DFS方法，收获也不少( •̀ ω •́ )✧
typedef struct TrieWords
{
char words[50];///存在的单词
int cnt;///存下次数
}TrieWords;
TrieWords CONTAINER[1000];///存下所有单词的容器
///不用DFS时text需要换成这个，有些区别
void Text()
{
container=0;
//1-以单个字符来输入文本，以空格来分割，将前面已经出现的单词插入root中
//以#为结束标志
char words[50];
int i=0,j=0;
printf("请输入文本(输入#代表结束):\n");
///插入词语
char ch='+';
int Flags=1;
while(1)
{
scanf("%c",&ch);
if((ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z'))
{
words[i++]=ch;
Flags=1;
}
else if(Flags==1)
{
words[i++]='\0';
Flags=0;
printf("words是:%s\n",words);
int Repos=0;
for(j=0;j<container;j++)
{
if(strcmp(CONTAINER[j].words,words)==0)
{
Repos=1;
break;
}
}
if(Repos==0)///还没重复，cnt为0
{
strcpy(CONTAINER[container++].words,words);
CONTAINER[container-1].cnt=1;
}
else ///发现已经出现，在j已经重复了，则cnt++
CONTAINER[j].cnt++;
///printf("length是：%d\n",strlen(words));
inserts(words);
///printf("过了insert\n");
i=0;
}
if(ch=='#') break;
}
///删除CONTAINER中重复的单词
}
//应用2统计所有出现过的单词词频
//找出所有单词并将其用query来求出每个单词的个数
char DEVIDE[50];
int Devide;
void Traves()
{
root=new trieNode(' ');///建立根节点
Text();
printf("下面是所有单词以及出现的次数：\n");
int i;
for(i=0;i<container;i++)
{
printf("%s：",CONTAINER[i].words);
printf("%d\n",CONTAINER[i].cnt);
}
}
完整代码（包含DFS遍历）
在一些基础代码上我加上了一些简单的可操作界面，部分界面如下，可直接运行尝试
全部代码已经上传，可以直接点击链接或者下载资源获取
链接:Trie树的插入、查询、删除和部分应用（单词的查询、单词出现频率/DFS和非DFS两种遍历）
附上参考网址：https://www.bilibili.com/video/BV1KQ4y1N7Je ，上面我对于trie树的许多基础内容都是参考了这个up主讲的，看视频可能更清楚，需要的可以去看看。