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;
}