Trie树的常见应用大总结（面试+附代码实现）
生活随笔
收集整理的這篇文章主要介紹了
Trie树的常见应用大总结（面试+附代码实现）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
（一）Trie的簡介
Trie樹，又稱字典樹，單詞查找樹或者前綴樹，是一種用于快速檢索的多叉樹結構，如英文字母的字典樹是一個26叉樹，數字的字典樹是一個10叉樹。他的核心思想是空間換時間，空間消耗大但是插入和查詢有著很優秀的時間復雜度。
（二）Trie的定義
typedef?struct?Trie_Node?? {?? ????char?count[15];??????//單詞前綴出現的次數??? ????struct?Trie_Node*?next[MAXN];????//指向各個子樹的指針??? ????bool?exist;????//標記結點處是否構成單詞??? }Trie;??
void?Insert(Trie?*root,?char*?s,char?*add)?? {?? ????Trie?*p=root;?? ????while(*s!='\0')?? ????{?? ????????if(p->next[*s-'a']==NULL)?? ????????{?? ????????????p->next[*s-'a']=createNode();?? ????????}?? ????????p=p->next[*s-'a'];?? ???????//?p->count=add;?? ????????++s;??? ????}?? ????p->exist=true;??? ????strcpy(p->count,add);?? }??
（2）查詢操作
和插入操作相仿，若查詢途中某一個結點并不存在，則直接就return返回。否則繼續下去，當字符串結束時，trie樹上也有結束標志，那么證明此字符串存在，return true； int?Search(Trie*?root,const?char*?s)?? {?? ????Trie?*p=root;?? ????while(*s!='\0')?? ????{?? ????????p=p->next[*s-'a'];?? ????????if(p==NULL)?? ????????return?0;?? ????????++s;?? ????}?? ????return?p->count;?? }??
void?del(Trie?*root)?? {?? ????for(int?i=0;i<MAXN;i++)?? ????{?? ????????if(root->next[i]!=NULL)?? ????????{?? ???????????del(root->next[i]);????? ????????}?? ????}?? //??free(root);????? ???delete?root;?? }??
void?Print(Trie?*root)?? {?? ????Trie?*p=root;?? ????if(p->exist)?? ????cout<<p->name<<":?"<<p->count<<endl;?? ????for(int?i=0;i<26;i++)?? ????{?? ????????if(p->next[i]!=NULL){?? ????????????Print(p->next[i]);?? ????????}?? ????}??? }???
（四）Trie樹的具體應用
（1）統計前綴出現的次數
這是Trie最基本的應用，每個結點的字母使用count記錄出現的次數即可。
這里提供一道題目，hdu 1251供大家練習。
//hdu?1251???統計前綴出現次數??? #include?<cstdio>?? #include?<iostream>?? #include?<string>?? #include?<cstring>?? using?namespace?std;?? const?int?MAXN=26;?? typedef?struct?Trie_Node?? {?? ????int?count;??????//單詞前綴出現的次數??? ????struct?Trie_Node*?next[MAXN];????//指向各個子樹的指針??? ????bool?exist;????//標記結點處是否構成單詞??? }Trie;?? Trie*?createNode()?? {?? ????//Trie*?p?=(Trie*)malloc(sizeof(Trie));?? ????Trie?*p=new?Trie;?? ????p->count=0;?? ????p->exist=false;?? ????memset(p->next,0,sizeof(p->next));?? ????return?p;?? }?? void?Insert(Trie?*root,?const?char*?s)?? {?? ????Trie?*p=root;?? ????while(*s!='\0')?? ????{?? ????????if(p->next[*s-'a']==NULL)?? ????????{?? ????????????p->next[*s-'a']=createNode();?? ????????}?? ????????p=p->next[*s-'a'];?? ????????p->count+=1;?? ????????++s;??? ????}?? ????p->exist=true;??? }?? ?? int?Search(Trie*?root,const?char*?s)?? {?? ????Trie?*p=root;?? ????while(*s!='\0')?? ????{?? ????????p=p->next[*s-'a'];?? ????????if(p==NULL)?? ????????return?0;?? ????????++s;?? ????}?? ????return?p->count;?? }?? ?? void?del(Trie?*root)?? {?? ????for(int?i=0;i<MAXN;i++)?? ????{?? ????????if(root->next[i]!=NULL)?? ????????{?? ???????????del(root->next[i]);????? ????????}?? ????}?? //??free(root);????? ???delete?root;?? }?? int?main()?? {?? ????char?s[15];?? ????bool?flag=false;?? ????Trie*?root=createNode();?? ????while(gets(s))?? ????{?? ????????if(flag)?? ????????{?? ???????????int?ans=Search(root,s);?? ???????????printf("%d\n",ans);???? ????????}????? ????????else?? ????????{?? ????????????if(strlen(s)!=0)?? ????????????Insert(root,s);?? ????????}?? ????????if(strlen(s)==0)?? ????????flag=true;???? ????}?? ????del(root);?? ????return?0;?? }??
（2）翻譯（密碼，明文）
給定一組字符串s，k我們輸入k則需要翻譯成s，也就是說兩者是映射關系。接下來我們給出一段話，讓你翻譯出正常的文章。用map固然簡便，但是Trie的效率更加高。只需要在k的結尾結點出記錄下s即可。
這里也提供一道題目，hdu 1075。(被注釋的是我原來的程序，wa了，有大神看出來麻煩告訴我一下，謝謝)。
/*? //hdu?1075映射?? #include?<cstdio>? #include?<iostream>? #include?<string>? #include?<cstring>? #include?<stdlib.h>? using?namespace?std;? const?int?MAXN=26;? typedef?struct?Trie_Node? {? ????char?count[15];??????//單詞前綴出現的次數?? ????struct?Trie_Node*?next[MAXN];????//指向各個子樹的指針?? ????bool?exist;????//標記結點處是否構成單詞?? }Trie;? Trie*?createNode()? {? ????Trie*?p?=(Trie*)malloc(sizeof(Trie));? ????p->exist=false;? ????memset(p->next,0,sizeof(p->next));? ????return?p;? }? void?Insert(Trie?*root,?char*?s,char?*add)? {? ????Trie?*p=root;? ????while(*s!='\0')? ????{? ????????if(p->next[*s-'a']==NULL)? ????????{? ????????????p->next[*s-'a']=createNode();? ????????}? ????????p=p->next[*s-'a'];? ???????//?p->count=add;? ????????++s;?? ????}? ????p->exist=true;?? ????strcpy(p->count,add);? }? ? ? ? void?Search(Trie*?root,?const?char*?s)? {? ????Trie?*p=root;? ????while(*s!='\0')? ????{? ????????if(p->next[*s-'a']==NULL)? ????????{??? ????????????printf("%s",s);? ????????????return?;? ????????}? ????? ????????p=p->next[*s-'a'];? ????????++s;? ????}? ????if(p->exist)? ????printf("%s",p->count);? ????else? ????printf("%s",s);? }? ? void?del(Trie?*root)? {? ????for(int?i=0;i<MAXN;i++)? ????{? ????????if(root->next[i]!=NULL)? ????????{? ???????????del(root->next[i]);???? ????????}? ????}? ????free(root);???? }? int?main()? {? ????char?text[3013],from[15],to[15];? ????Trie*?root=createNode();? ????scanf("%s",from);? ????while(scanf("%s",from),strcmp(from,"END"))? ????{? ????????scanf("%s",to);? ????????Insert(root,to,from);? ????}? ????scanf("%s",from);? ????getchar();? ????while(gets(text),strcmp(text,"END"))? ????{? ????????int?len=strlen(text);? ????????for(int?i=0;i<len;i++)? ????????{? ????????????if(islower(text[i]))? ????????????{? ????????????????int?j=0;? ????????????????char?temp[15];? ????????????????memset(temp,'\0',sizeof(temp));? ????????????????while(islower(text[i]))? ????????????????temp[j++]=text[i++];? ????????????????Search(root,temp);? ?????????????? ????????????}? ????????????if(!islower(text[i]))? ????????????printf("%c",text[i]);? ????????}? ????????printf("\n");? ????}? ????return?0;? }? */?? ?? #include<stdio.h>?? #include<string.h>?? #include<stdlib.h>?? #include<string>?? ?? using?namespace?std;?? ?? struct?node{?? ????char?dic[15];?? ????node?*?next[26];?? ????bool?flag;?? }*root;?? ?? node?*build()?? {?? ????node?*p=(node?*)malloc(sizeof(node));?? ????for(int?i=0;i<26;i++)?? ????????p->next[i]=NULL;?? ????p->flag=false;?? ????return?p;?? }?? ?? void?insert(char?*earth,char?*mars)?? {?? ????int?len=strlen(mars);?? ????node?*p;?? ????p=root;?? ????for(int?i=0;i<len;i++)?? ????{?? ????????if(p->next[mars[i]-'a']==NULL)?? ????????????p->next[mars[i]-'a']=build();?? ????????p=p->next[mars[i]-'a'];?? ????}?? ????p->flag=true;?? ????strcpy(p->dic,earth);?? }?? ?? void?query(char?*earth)?? {?? ????int?len=strlen(earth);?? ????node?*p;?? ????p=root;?? ????for(int?i=0;i<len;i++)?? ????{?? ????????if(p->next[earth[i]-'a']==NULL)?? ????????{?? ????????????printf("%s",earth);?? ????????????return;?? ????????}?? ????????p=p->next[earth[i]-'a'];?? ????}?? ????if(p->flag)?? ????????printf("%s",p->dic);?? ????else?? ????????printf("%s",?earth);?? }?? ?? ?? int?main()?? {?? ????char?earth[15],mars[15],ask[3010];?? ?? ?? ????scanf("%s",earth);?? ????root=build();?? ????while(scanf("%s",earth),strcmp(earth,"END"))?? ????{?? ????????scanf("%s",mars);?? ????????insert(earth,mars);?? ????}?? ?? ?? ????scanf("%s",earth);?? ????getchar();?? ????while(gets(ask),strcmp(ask,"END"))?? ????{?? ????????int?len=strlen(ask);?? ????????for(int?i=0;i<len;i++)?? ????????{?? ????????????if(islower(ask[i]))?? ????????????{?? ????????????????int?j=0;?? ????????????????memset(earth,'\0',sizeof(earth));?? ????????????????while(islower(ask[i]))?? ????????????????????earth[j++]=ask[i++];?? ????????????????query(earth);?? ????????????}?? ????????????if(!islower(ask[i]))?? ????????????????printf("%c",ask[i]);?? ????????}?? ????????printf("\n");?? ????}?? ?? ????return?0;?? }??
（3）實現搜索引擎的熱門搜索排名
我的初步想法是和(1)類似，對（1）中的trie進行先序遍歷，將字符串和出現次數存進一個結構體，最后對這個數組進行快速排序，時間復雜度為O(nlogn),看網上說可以利用分治+trie
+最小堆，我還沒有仔細搞清楚，以后研究完在添加。
（4）輸入自動補全
其實原理都差不多，把字符串結尾處的結點當作root，進行先序遍歷，即可得出所有以輸入的字符串為前綴的答案。
/?自動補全??? #include?<cstdio>?? #include?<iostream>?? #include?<string>?? #include?<cstring>?? using?namespace?std;?? const?int?MAXN=26;?? typedef?struct?Trie_Node?? {?? ????int?count;??????//單詞出現的次數??? ????struct?Trie_Node*?next[MAXN];????//指向各個子樹的指針??? ????bool?exist;????//標記結點處是否構成單詞??? ????char?name[15];?? }Trie;?? Trie*?createNode()?? {?? ????Trie*?p?=(Trie*)malloc(sizeof(Trie));?? ????p->count=0;?? ????p->exist=false;?? ????memset(p->next,0,sizeof(p->next));?? ????return?p;?? }?? void?Insert(Trie?*root,char*?word)?? {?? ????Trie?*p=root;?? ????char?*s=word;?? ????while(*s!='\0')?? ????{?? ????????if(p->next[*s-'a']==NULL)?? ????????{?? ????????????p->next[*s-'a']=createNode();?? ????????}?? ????????p=p->next[*s-'a'];?? ????????++s;??? ????}?? ?????p->exist=true;??? ??????p->count+=1;?? ???strcpy(p->name,word);?? }?? ?? Trie*?Search(Trie*?root,?char*?s)?? {?? ????Trie?*p=root;?? ????while(*s!='\0')?? ????{?? ????????p=p->next[*s-'a'];?? ????????if(p==NULL)?? ????????return?0;?? ????????++s;?? ????}?? ????return?p;?? }?? ?? void?del(Trie?*root)?? {?? ????for(int?i=0;i<MAXN;i++)?? ????{?? ????????if(root->next[i]!=NULL)?? ????????{?? ???????????del(root->next[i]);????? ????????}?? ????}?? ????free(root);????? ?? }?? void?Print(Trie?*root)?? {?? ????Trie?*p=root;?? ????if(p->exist)?? ????cout<<p->name<<":?"<<p->count<<endl;?? ????for(int?i=0;i<26;i++)?? ????{?? ????????if(p->next[i]!=NULL){?? ????????????Print(p->next[i]);?? ????????}?? ????}??? }??? int?main()?? {?? ????char?s[15];?? ????Trie*?root=createNode();?? ????for(int?i=0;i<5;i++)?? ????{?? ????????cin>>s;?? ????????Insert(root,s);?? ????}?? ????while(cin>>s)?? ????{?? ????????Trie?*ans=Search(root,s);?? ????????if(ans)?? ????????Print(ans);?? ????}?? ????del(root);?? ????return?0;?? }?? 原文地址：?http://blog.csdn.net/nk_test/article/details/47836119
Trie樹，又稱字典樹，單詞查找樹或者前綴樹，是一種用于快速檢索的多叉樹結構，如英文字母的字典樹是一個26叉樹，數字的字典樹是一個10叉樹。他的核心思想是空間換時間，空間消耗大但是插入和查詢有著很優秀的時間復雜度。
（二）Trie的定義
Trie樹的鍵不是直接保存在節點中，而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的前綴（prefix）,從根節點到當前結點的路徑上的所有字母組成當前位置的字符串，結點可以保存當前字符串、出現次數、指針數組(指向子樹)以及是否是結尾標志等等。
[cpp]?view plain?copy
Trie樹可以利用字符串的公共前綴來節約存儲空間，如下圖所示：
它有3個基本性質：
(1) 根節點不包含字符，除根節點外每一個節點都只包含一個字符。
(2) 從根節點到某一節點，路徑上經過的字符連接起來，為該節點對應的字符串。
(3) 每個節點的所有子節點包含的字符都不相同。
（三）Trie樹的基本操作
（1）插入操作
按下標索引逐個插入字母，若當前字母存在則繼續下一個，否則new出當前字母的結點，所以插入的時間復雜度只和字符串的長度n有關，為O(n)。
[cpp]?view plain?copy
和插入操作相仿，若查詢途中某一個結點并不存在，則直接就return返回。否則繼續下去，當字符串結束時，trie樹上也有結束標志，那么證明此字符串存在，return true；
[cpp]?view plain?copy
（3）刪除操作
一般來說，對Trie單個結點的刪除操作不常見，所以我在這里也只提供遞歸刪除整個樹的操作
[cpp]?view plain?copy（4）遍歷操作
如果我們想要將trie中的字符串排序輸出，直接先序遍歷即可。
[cpp]?view plain?copy
（1）統計前綴出現的次數
這是Trie最基本的應用，每個結點的字母使用count記錄出現的次數即可。
這里提供一道題目，hdu 1251供大家練習。
[cpp]?view plain?copy
給定一組字符串s，k我們輸入k則需要翻譯成s，也就是說兩者是映射關系。接下來我們給出一段話，讓你翻譯出正常的文章。用map固然簡便，但是Trie的效率更加高。只需要在k的結尾結點出記錄下s即可。
這里也提供一道題目，hdu 1075。(被注釋的是我原來的程序，wa了，有大神看出來麻煩告訴我一下，謝謝)。
[cpp]?view plain?copy
我的初步想法是和(1)類似，對（1）中的trie進行先序遍歷，將字符串和出現次數存進一個結構體，最后對這個數組進行快速排序，時間復雜度為O(nlogn),看網上說可以利用分治+trie
+最小堆，我還沒有仔細搞清楚，以后研究完在添加。
（4）輸入自動補全
其實原理都差不多，把字符串結尾處的結點當作root，進行先序遍歷，即可得出所有以輸入的字符串為前綴的答案。
[cpp]?view plain?copy
總結
以上是生活随笔為你收集整理的Trie树的常见应用大总结（面试+附代码实现）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 无需Root也能Hook？——Depox
- 下一篇： 基于Android的ELF PLT/GO