字典树模板

字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

字典树主要用来处理单词前缀问题。如统计难题 ， Phone List

模板1：

const int MAX=10;typedef struct node{    struct node *next[MAX];    int flag;  //标记是否是一个单词}Trie;Trie *root;/*root要初始化root=(Trie *)malloc(sizeof(Trie));root->flag=0;for(int i=0;i<MAX;i++){    root->next[i]=NULL;}*/int createTrie(char *str) //创建一棵字典树,与查找合并{    int len = strlen(str);    Trie *p = root, *q;    for(int i=0; i<len; i++)    {        if(p->flag==1) //查找1；说明已有一个单词作为前缀,比如119,119895            return 1;        int id = str[i]-'0'; //数字字符        if(p->next[id] == NULL)        {            q = (Trie *)malloc(sizeof(Trie));            q->flag = 0;              for(int j=0; j<MAX; j++)                q->next[j] = NULL;            p->next[id] = q;        }        p = p->next[id];    }    for(int i=0;i<MAX;i++){ //查找2；判断该单词是否是其它单词的前缀，如119895，119        if(p->next[i]!=NULL)            return 1;    }    p->flag=1; //一个单词    return 0;}void dealTrie(Trie* T) //清理内存root{    for(int i=0;i<MAX;i++)    {        if(T->next[i]!=NULL)            dealTrie(T->next[i]);    }    free(T);}
模板2：
const int MAX=26;typedef struct node{    struct node *next[MAX];    int flag;  //该字母出现的次数}Trie;Trie *root;/*root要初始化root=(Trie *)malloc(sizeof(Trie));root->flag=0;for(int i=0;i<MAX;i++){    root->next[i]=NULL;}*/void createTrie(char *str) //创建一棵字典树{    int len = strlen(str);    Trie *p = root, *q;    for(int i=0; i<len; i++)    {        int id = str[i]-'a'; //小写字母        if(p->next[id] == NULL)        {            q = (Trie *)malloc(sizeof(Trie));            q->flag = 0;            for(int j=0; j<MAX; j++)                q->next[j] = NULL;            p->next[id] = q;        }        p = p->next[id];        p->flag++;    }}int findTrie(char *str) //找出以str字符串为前缀的单词的数量.{    int len = strlen(str);    Trie *p = root;    for(int i=0; i<len; i++)    {        int id = str[i]-'a';        p = p->next[id];        if(p == NULL)   //若为空集，表示不存以此为前缀的串            return 0;    }    return p->flag;}void dealTrie(Trie* T) //清理内存root{    for(int i=0;i<MAX;i++)    {        if(T->next[i]!=NULL)            dealTrie(T->next[i]);    }    free(T);}