Trie树(单纯词查找树或键树)

Trie树(单词查找树或键树)
Trie树
  Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
   Trie是一颗存储多个字符串的树。相邻节点间的边代表一个字符，这样树的每条分支代表一则子串，而树的叶节点则代表完整的字符串。和普通树 不同的地方是，相同的字符串前缀共享同一条分支。还是例子最清楚。给出一组单词，inn, int, at, age, adv, ant, 我们可以得到下面的Trie：


tire树的查找时间复杂度为O(n)
实现代码(借鉴了某位博主的代码):

 

Output
In this problem, you have to output the translation of the history book.

 

Sample Input
START
from fiwo
hello difh
mars riwosf
earth fnnvk
like fiiwj
END
START
difh, i'm fiwo riwosf.
i fiiwj fnnvk!
END
 

Sample Output
hello, i'm from mars.
i like earth!

Hint
Huge input, scanf is recommended.

题意:第一个START到END之间是字典表,前面代表原词,后面代表火星文,现在给你一个句子,里面有火星文,请翻译句子
#include <iostream>using namespace std;const int branch = 10;//注意点:记得每次释放字典树,因为为多个用例typedef struct trie_Node{bool isword;struct trie_Node *next[branch];trie_Node() : isword(false){memset(next, NULL, sizeof(next));}}*pTrie_Node;class Trie{private:pTrie_Node root;public:Trie(){root = new trie_Node();}pTrie_Node getRoot(){return root;}void insert(const char *word);bool search(pTrie_Node cur);void destory(pTrie_Node cur);};void Trie::insert(const char *word){pTrie_Node loc = root;while(*word && loc){if(loc->next[*word - '0'] == NULL){pTrie_Node tmp = new trie_Node();loc->next[*word - '0'] = tmp;}loc = loc->next[*word - '0'];word++;}loc->isword = true;}bool Trie::search(pTrie_Node cur){int i;if(cur->isword)for(i = 0; i < branch; i++)if(cur->next[i] != NULL)return false;for(i = 0; i < branch; i++)if(cur->next[i] != NULL)if(!search(cur->next[i]))return false;return true;}void Trie::destory(pTrie_Node cur){for(int i = 0; i < branch; i++)if(cur->next[i] != NULL)destory(cur->next[i]);delete cur;}int main(){int t, n, i;char phone[11];cin>>t;while(t--){cin>>n;Trie t;for(i = 0; i < n; i++){cin>>phone;t.insert(phone);}if(!t.search(t.getRoot()))cout<<"NO"<<endl;elsecout<<"YES"<<endl;t.destory(t.getRoot()); //这句很重要,不然要超内存}return 0;}