大家好，又见面了，我是风君子，今天给大家准备了Idea注册码。
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 Insertchar *word,TrieNode *root) 16 17 { 18 int i; 19 TrieNode *cur; 20 ifword[0]=='\0') 21 return; 22 cur=root; 23 fori=0;word[i]!='\0';i++) 24 { 25 ifcur->next[word[i]]==NULL) 26 { 27 TrieNode *newNode = TrieNode *)mallocsizeofTrieNode)); 28 memsetnewNode,0,sizeofTrieNode)); 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 ConstructTrieNode *&root) 40 { 41 char inStr[MAXLEN]; 42 int size=0; 43 root = TrieNode *)mallocsizeofTrieNode)); 44 memsetroot,0,sizeofTrieNode)); 45 while1) 46 { 47 scanf"%s",inStr); 48 ifstrcmpinStr,"*")==0) 49 break; 50 InsertinStr,root); 51 } 52 return; 53 } 54 55 //遍历整棵树 56 void TraverseTrieNode *curP) 57 { 58 static char theWord[MAXLEN]; 59 static int pos=0; 60 int i; 61 ifcurP==NULL) 62 return; 63 ifcurP->count) 64 { 65 theWord[pos]='\0'; 66 printf"%s:%d\n",theWord,curP->count); 67 } 68 fori=0;i<MAX;i++) 69 { 70 theWord[pos++]=i; 71 //从这句话可以看出在递归调用子节点前，子节点的值已经加入到单词中了 72 TraversecurP->next[i]); 73 pos--; 74 } 75 return; 76 } 77 78 //查找一个单词是不是在树中 79 bool FindTrieNode *root,char *word) 80 { 81 int i; 82 TrieNode *cur; 83 cur=root; 84 fori=0;word[i]!='\0';i++) 85 { 86 ifcur->next[word[i]]==NULL) 87 { 88 return false; 89 } 90 cur=cur->next[word[i]]; 91 } 92 93 ifcur->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 Constructroot); 104 printf"\n"); 105 Traverseroot); 106 printf"\n"); 107 while1) 108 { 109 scanf"%s",str); 110 ifstrcmpstr,"*")==0) 111 break; 112 printf"%s:%d\n",str,Findroot,str)); 113 } 114 115 return 0; 116 }
推荐：http://www.cnblogs.com/roucheng/p/wendang.html