字典树（Trie树）

全栈程序员站长

发布于 2022-07-15 08:25:06

51100

代码可运行

文章被收录于专栏：全栈程序员必看全栈程序员必看

运行总次数：0

代码可运行

大家好，又见面了，我是全栈君

1. trie基础

(1) 是什么？

Trie，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。

(2) 性质

根节点不包含字符，除根节点外每一个节点都只包含一个字符
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
每个节点的所有子节点包含的字符都不相同

例如，单词序列a, to, tea, ted, ten, i, in, inn，对应的trie。

(3) 应用

用于统计和排序大量的字符串，但不仅限于字符串，所以经常被搜索引擎系统用于文本词频统计。

(4) 优点

最大限度地减少无谓的字符串比较
查询效率比哈希表高

2. 一个例子

  1 #include <stdio.h>  
  2 #include <string.h>  
  3 #include <stdlib.h>  
  4   
  5 #define MAX 256//ascii码有256个字符，故每棵树的子节点最多有256个  
  6 #define MAXLEN 256//单词最长为256  
  7   
  8 typedef struct TrieNode  
  9 {  
 10     int count;  
 11     struct TrieNode *next[MAX];  
 12 }TrieNode;    
 13   
 14 //插入一个单词  
 15 void Insert(char *word,TrieNode *root)  
 16   
 17 {  
 18     int i;  
 19     TrieNode *cur;  
 20     if(word[0]=='\0')  
 21         return;  
 22     cur=root;  
 23     for(i=0;word[i]!='\0';i++)  
 24     {  
 25         if(cur->next[word[i]]==NULL)  
 26         {  
 27             TrieNode *newNode = (TrieNode *)malloc(sizeof(TrieNode));  
 28             memset(newNode,0,sizeof(TrieNode));  
 29             cur->next[word[i]]=newNode;  
 30         }  
 31         cur=cur->next[word[i]];  
 32     }  
 33   
 34     cur->count++;  
 35     return;  
 36 }  
 37   
 38 //创建树输入每个单词，以回车结束，则单词被插入树中，碰到*停止树的创建  
 39 void Construct(TrieNode *&root)  
 40 {  
 41      char inStr[MAXLEN];  
 42      int size=0;  
 43      root = (TrieNode *)malloc(sizeof(TrieNode));  
 44      memset(root,0,sizeof(TrieNode));  
 45      while(1)  
 46      {  
 47          scanf("%s",inStr);  
 48          if(strcmp(inStr,"*")==0)  
 49              break;  
 50          Insert(inStr,root);  
 51      }  
 52      return;  
 53 }  
 54   
 55 //遍历整棵树  
 56 void Traverse(TrieNode *curP)  
 57 {  
 58     static char theWord[MAXLEN];  
 59     static int pos=0;   
 60     int i;  
 61     if(curP==NULL)  
 62         return;  
 63     if(curP->count)  
 64     {  
 65         theWord[pos]='\0';  
 66         printf("%s:%d\n",theWord,curP->count);  
 67     }  
 68     for(i=0;i<MAX;i++)  
 69     {  
 70         theWord[pos++]=i;   
 71 //从这句话可以看出在递归调用子节点前，子节点的值已经加入到单词中了  
 72         Traverse(curP->next[i]);   
 73         pos--;    
 74     }  
 75     return;  
 76 }  
 77   
 78 //查找一个单词是不是在树中  
 79 bool Find(TrieNode *root,char *word)  
 80 {  
 81     int i;  
 82     TrieNode *cur;  
 83     cur=root;  
 84     for(i=0;word[i]!='\0';i++)  
 85     {  
 86         if(cur->next[word[i]]==NULL)  
 87         {  
 88             return false;  
 89         }  
 90         cur=cur->next[word[i]];  
 91     }  
 92   
 93     if(cur->count)  
 94         return true;  
 95     else  
 96         return false;  
 97 }  /* 何问起 hovertree.com */
 98   
 99 int main()    
100 {    
101     TrieNode *root;  
102     char str[MAXLEN];  
103     Construct(root);    
104     printf("\n");    
105     Traverse(root);    
106     printf("\n");    
107     while(1)  
108     {  
109         scanf("%s",str);  
110         if(strcmp(str,"*")==0)  
111             break;  
112         printf("%s:%d\n",str,Find(root,str));   
113     }  
114   
115     return 0;    
116 }