字典树（Trie树）

大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。

1. trie基础

(1) 是什么？

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

(2) 性质

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

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

字典树（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 }