http://www.cnblogs.com/wanglikai91/archive/2011/10/11/2207688.html
http://blog.csdn.net/v_july_v/article/details/6897097
Trie数据结构
Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
它有3个基本性质：
- 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
- 每个节点的所有子节点包含的字符都不相同。
Trie树的构造
Trie树节点分两部分，一部分用来记录该节点的值，另外一部分用来记录孩子节点
初始时只有一个根节点，根节点并不存储数据，插入的时候根据当前字符来判断应该沿着哪条路径走，如果节点不存在则新建，走到所要查找单词的最后一个字符时，把该单词的值设为一表示存在
查找节点的时候，沿着根节点走，直到查找到单词最后一个字符，判断该节点的值是否为1，如果是1表示存在所查找的单词。或者如果沿着根节点走到一个空节点，表明不存在该单词。
1 #include <stdio.h> 2 #include <string.h> 3 /* 构建Trie结构 */ 4 struct trie 5 { 6 int count; 7 trie * child[26]; /* 用来存储孩子节点 */ 8 trie(){ 9 count=0; 10 for(int i=0;i<26;i++) 11 child[i]=NULL; 12 } 13 }; 14 15 trie * root; /* 表示根节点 */ 16 17 void insert(char * word) 18 { 19 trie * location = root; 20 while(*word!='\0') 21 { 22 int charAt=*word; 23 if(charAt>='a' && charAt <='z') /* 根据单词决定走哪条路径 */ 24 charAt-='a'; 25 else return; 26 if(location->child[charAt]==NULL) /* 节点如果不存在，则新建 */ 27 location->child[charAt]=new trie; 28 location=location->child[charAt]; 29 word++; 30 } 31 location->count++; /* 可以记录该单词的数量 */ 32 } 33 34 int search(char * word) 35 { 36 trie * location = root; 37 while(*word!='\0' && location != NULL) 38 { 39 int charAt = *word; 40 if(charAt>='a' && charAt <= 'z') 41 charAt-='a'; 42 else 43 return -1; 44 location=location->child[charAt]; /* 沿着孩子节点方向走 */ 45 word++; 46 } 47 if(location==NULL) /* 节点为空，表明不存在该单词 */ 48 return 0; 49 else 50 return location->count; 51 } 52 53 char sequence[20]; 54 int pt = 0; 55 56 /* 打印整棵树表示的所有单词 */ 57 void printTrie(trie * node) 58 { 59 int i; 60 for(i=0;i<26 && node->child[i]==NULL;i++); 61 if(i>=26) 62 { 63 printf("%.*s %d\n", pt, sequence, node->count); /* 打印单词以 64 * 及出现的次 65 * 数 */ 66 return; 67 } 68 69 for(;i<26;i++){ 70 if(node->child[i]!=NULL) 71 { 72 sequence[pt++]=i+'a'; 73 printTrie(node->child[i]); 74 pt--; 75 } 76 } 77 } 78 /* 释放节点 */ 79 void freeTrie(trie * node) 80 { 81 if(node == NULL) 82 return; 83 for(int i=0;i<26;i++) 84 freeTrie(node->child[i]); 85 delete node; 86 node=NULL; 87 } 88 89 int main(int argc,char * argv[]) 90 { 91 root=new trie; /* 新建根节点 */ 92 insert("hello"); 93 insert("hi"); 94 insert("heihei"); 95 insert("hi"); 96 int result = search("hi"); /* 查找 */ 97 printf("%d\n",result); 98 result = search("ke"); 99 printf("%d\n",result); 100 freeTrie(root); 101 return 0; 102 }
题例分析
题意：给定字符串，从开头到任意位置之间的字符串称为该字符串的前缀，如对于carbon来说, ”c”, “ca”,”car”都是它的前缀字符串，空串不作为字符串的前缀，字符串本身也可看做是自己的前缀字符串，给出一系列单词，找出能够唯一表示它们的前缀字符串，前缀字符串和某个字符串相同时，则唯一表示该字符串而不能表示其它字符串，例如，给定caramel，carbon，car，则前缀”car”毫无疑问表示car而不能表示其它字符串
输入示例：
carbohydrate cart carburetor caramel caribou carbonic cartilage carbon carriage carton car carbonate
输出示例：
carbohydrate carboh cart cart carburetor carbu caramel cara caribou cari carbonic carboni cartilage carti carbon carbon carriage carr carton carto car car carbonate carbona
分析：要想让前缀字符串唯一的表示一个字符串，则一个字符串的前缀字符串不能是另外一个字符串前缀字符串的子串, 由于需要找前缀字符串，所以最好的方法是使用Trie树，字符串插入Trie树的时候，将从根到叶子节点路径上的每个节点的值都加一，查找字符串的时候沿着根到叶子的方向走，如果碰到某个子节点的值小于等于1，表明该字符为当前所查找字符串单独所有，从根到该节点所组成的前缀可作为该字符串的最短前缀字符串。
1 #include <stdio.h> 2 #include <string.h> 3 4 struct trie 5 { 6 int count; 7 trie * child[26]; 8 trie(){ 9 count=0; 10 for(int i=0;i<26;i++) 11 child[i]=NULL; 12 } 13 }; 14 15 trie * root; 16 char s[1003][21]; 17 18 void insert(char * word) 19 { 20 trie * location = root; 21 while(*word!='\0') 22 { 23 int charAt=*word++; 24 if(charAt>='a' && charAt <='z') 25 charAt-='a'; 26 location->count++; 27 if(location->child[charAt]==NULL) 28 location->child[charAt]= new trie; 29 location=location->child[charAt]; 30 } 31 location->count++; 32 } 33 34 void search(char * word) 35 { 36 trie * location = root; 37 while(*word != '\0' && location != NULL) 38 { 39 int charAt = *word++; 40 if(location->count<=1) 41 { 42 putchar('\n'); 43 return; 44 } 45 putchar(charAt); 46 if(charAt>='a' && charAt <= 'z') 47 charAt-='a'; 48 location=location->child[charAt]; 49 } 50 putchar('\n'); 51 } 52 53 void freeTrie(trie * node) 54 { 55 if(node == NULL) 56 return; 57 for(int i=0;i<26;i++) 58 freeTrie(node->child[i]); 59 delete node; 60 node=NULL; 61 } 62 63 int main(int argc,char * argv[]) 64 { 65 freopen("in","r",stdin); 66 root=new trie; 67 int i=0; 68 while(scanf("%s",s[i])!=EOF) 69 { 70 insert(s[i]); 71 i++; 72 } 73 for(int j=0;j<i;j++) 74 { 75 printf("%s ",s[j]); 76 search(s[j]); 77 } 78 freeTrie(root); 79 return 0; 80 }
模版
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 using namespace std; 6 7 const int SIZE = 26; 8 class T_Node //节点类 9 { 10 public: 11 bool terminal; //是否是一个单词的结尾 12 T_Node *next[SIZE]; //节点儿子指针 13 public: 14 T_Node(); 15 }; 16 class Trie 17 { 18 public: 19 T_Node *root; //trie树的根 20 public: 21 Trie(); 22 void Insert(string); //插入 23 bool Find(string); //查找 24 bool Delete(string); //删除 25 }; 26 27 T_Node::T_Node() //节点构造函数，单词结尾设置为FALSE，初始化指针为空 28 { 29 terminal = false; 30 memset(next, NULL, sizeof(next)); 31 } 32 33 Trie::Trie() //Trie树构造函数，建立根节点 34 { 35 root = new T_Node; 36 } 37 38 void Trie::Insert(string s) //插入 39 { 40 T_Node *p = root; //遍历指针*p初始化为根节点指针 41 int len = s.size(), num; //len单词长度 42 for (int i = 0; i < len; ++i) 43 { 44 num = s[i] - 'a'; //num当前单词对应表位置 45 if (p->next[num] == NULL) 46 { 47 p->next[num] = new T_Node; //当前字母指针不存在就建立新节点 48 } 49 p = p->next[num]; 50 } 51 p->terminal = true; 52 } 53 54 bool Trie::Find(string s) //查找 55 { 56 T_Node *p = root; 57 int len = s.size(), num; 58 for (int i = 0; i < len; ++i) 59 { 60 num = s[i] - 'a'; 61 if (p->next[num] == NULL) //某个字母不存在 62 { 63 return false; 64 } 65 p = p->next[num]; 66 } 67 if (!p->terminal) return false; //单词没有在这里结尾 68 return true; 69 } 70 71 bool Trie::Delete(string s) //删除单词 72 { 73 T_Node *stack[105]; //用栈记录经过的节点 74 int top = 0; 75 T_Node *p = root; 76 int len = s.size(), num; 77 for (int i = 0; i < len; ++i) 78 { 79 num = s[i] - 'a'; 80 if (p->next[num] == NULL) //没有这个单词 81 { 82 return false; 83 } 84 p = p->next[num]; 85 stack[top++] = p; 86 } 87 if (!p->terminal) //没有这个单词 88 { 89 return false; 90 } 91 else 92 { 93 p->terminal = false; //去除标记 94 bool flag = true; //是否有冗余节点 95 while (flag && top > 0) 96 { 97 if (p->terminal) 98 { 99 flag = false; 100 } 101 else 102 { 103 for (int i = 0; i < SIZE; ++i) 104 { 105 if (p->next[i] != NULL) 106 { 107 flag = false; 108 break; 109 } 110 } 111 } 112 if (flag) //如果有冗余节点则删除 113 { 114 delete p; 115 } 116 p = stack[--top]; 117 } 118 } 119 return true; 120 } 121 122 int main() 123 { 124 Trie tree; 125 string s; 126 s = "inn"; 127 tree.Insert(s); 128 s = "int"; 129 tree.Insert(s); 130 s = "tea"; 131 tree.Insert(s); 132 s = "ten"; 133 tree.Insert(s); 134 printf("Inserted 'inn', 'int', 'tea', 'ten'\n"); 135 printf("Find:\n"); 136 s = "ten"; 137 if (tree.Find(s)) 138 { 139 cout << s << " exist!" << endl; 140 } 141 else cout << s << " not exist!" << endl; 142 s = "itt"; 143 if (tree.Find(s)) 144 { 145 cout << s << " exist!" << endl; 146 } 147 else cout << s << " not exist!" << endl; 148 printf("Delete:\n"); 149 s = "ten"; 150 if (tree.Delete(s)) 151 { 152 cout << s << " deleted!" << endl; 153 } 154 else cout << s << " not exist!" << endl; 155 s = "itt"; 156 if (tree.Delete(s)) 157 { 158 cout << s << " deleted!" << endl; 159 } 160 else cout << s << " not exist!" << endl; 161 printf("Check:\n"); 162 s = "ten"; 163 if (tree.Find(s)) 164 { 165 cout << s << " exist!" << endl; 166 } 167 else cout << s << " not exist!" << endl; 168 return 0; 169 }