Trie树，又称为字典树，是一种树形结构，是一种哈希树的变种，是一种用于快速检索的多叉树数据结构。典型应用是用于统计和排序、查询大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本的词频统计等。

    找了一个简单的小例子来实现trie树的原理：

#include 
     
      using namespace std;const int branchNum = 26;int i;struct Trie_node{    bool isStr; //记录此处是否构成一个串。    Trie_node *next[branchNum];//指向各个子树的指针,下标0-25代表26字符    Trie_node():isStr(false)    {        memset(next,NULL,sizeof(next));    }};class Trie{public:    Trie();    void insert(const char* word);    bool search(char* word);    void deleteTrie(Trie_node *root);private:    Trie_node* root;};Trie::Trie(){    root = new Trie_node();}void Trie::insert(const char* word){    Trie_node *location = root;    while(*word)    {        if(location->next[*word-'a'] == NULL)        {            Trie_node *tmp = new Trie_node();            location->next[*word-'a'] = tmp;        }           location = location->next[*word-'a'];        word++;    }    location->isStr = true;}bool Trie::search(char *word){    Trie_node *location = root;    while(*word && location)    {        location = location->next[*word-'a'];        word++;    }    return(location!=NULL && location->isStr);}void Trie::deleteTrie(Trie_node *root){    for(i = 0; i < branchNum; i++)    {        if(root->next[i] != NULL)        {            deleteTrie(root->next[i]);        }    }    delete root;}int main(){    Trie t;    t.insert("a");            t.insert("abandon");    char * c = "abandoned";    t.insert(c);    t.insert("abashed");    if(t.search("abashed"))        printf("true\n");    return 0;}
     

    如果有多个字符串需要用trie树返回一个哈希值(不同的字符串返回的哈希值不相同)，则可以在每个节点存储一个额外的值，也就是在上述代码 isStr = true的情况下，会有个值来记录它对应的哈希值hash_value;

   (1) 设置一个递增变量v = 1;

   (2) 字符串数组 char *a[N];hash_v[N];

   (3) for(i=0;i<N;i++  )  hash_v[i] = insert(*a[i]);,  如果*a[i]字符串之前没有出现过，hash_v[i]= v++;  否则hash_v[i] = (串尾节点的hash_value)。

    在字符串哈希中，如果要求的重复度不能高，则可以考虑用trie树。