字典樹又稱單詞查找樹，Trie樹，是一種樹形結(jié)構，是一種哈希樹的變種。典型應用是用于統(tǒng)計，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。它的優(yōu)點是：利用字符串的公共前綴來節(jié)約存儲空間，最大限度地減少無謂的字符串比較，查詢效率比哈希表高。

字典樹主要用來處理單詞前綴問題。如統(tǒng)計難題 ， 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) //創(chuàng)建一棵字典樹,與查找合并{    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'; //數(shù)字字符        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) //清理內(nèi)存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;  //該字母出現(xiàn)的次數(shù)}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) //創(chuàng)建一棵字典樹{    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字符串為前綴的單詞的數(shù)量.{    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) //清理內(nèi)存root{    for(int i=0;i<MAX;i++)    {        if(T->next[i]!=NULL)            dealTrie(T->next[i]);    }    free(T);}