首页 > 代码库 > hiho_1014_Trie_Tree
hiho_1014_Trie_Tree
http://hihocoder.com/problemset/problem/1014
这个树感觉像是26叉树～ 写起来和普通的二叉树差不多。
<g++> 编译～
对比:
struct BinayNode{ int data; BinaryNode *l,*r; // 二叉的，有两个子树，可以写成 BinaryNode *son[2]; BinaryNode (int x=0,BinaryNode *l=NULL, BinaryNode *r=NULL):data(x),l(ll),r(rr) {} }
和二叉排序树相比，只是在节点上的值data的意义不同罢了～
看到维基下面好多种树wa～目前知道的 ：
BST AVL B B+..树，这些是基于数字大小排序的树
堆算是一种吧。
trie树是字典树，我觉得和BST差不多，排序的规则是字母，不包含在节点上，而在子树的顺序，即固定26棵树，来一个字母，它放在哪棵子树上是确定的，我感觉比起平衡二叉树要稳定得多，AVL扭来扭去的因为排序是对结点值的排序，而字典树是排好序的。
字典树就像是我们平时查字典一样～所以说，某些算法反映了更快捷的生活方式～ 好神奇啊～
const int alpha=26;struct TrieNode{ int cnt; TrieNode *next[26]; TrieNode(){ cnt=0; for(int i=0;i<alpha;++i) next[i]=NULL; }};int n;string s;int main(){ TrieNode *dic=new TrieNode; dic->cnt=-1; TrieNode *cur=NULL; cin >> n; /* 插入 */ while(n--){ cin >> s; cur = dic; for(int i=0;i<s.size();++i) { int index=s[i]-‘a‘; if(NULL==cur->next[index]) cur->next[index] = new TrieNode; cur->next[index]->cnt++; cur=cur->next[index]; } } cin >> n; /* 查找 */ while(n--){ cin >> s; cur = dic; for(int i=0;i<s.size();++i){ cur=cur->next[s[i]-‘a‘]; if(NULL==cur) break; } if(NULL==cur) cout << "0" << endl; else cout << cur->cnt << endl; } return 0;}
hiho_1014_Trie_Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。