本文共 2493 字，大约阅读时间需要 8 分钟。

我是小脆皮， 今天写一个字典树的博文~~~

字典树，就是n叉树。因为26个英文字母所以我这里就取26个叉了。

他的数据结构定义如下：

typedef struct node{    int nFlag;   //标记到此是否有单词    char* pStr;  //如果nFlag = 1， 此处则有单词释义    struct node *pList[26]; //26个指针， 代表 a~z }TrieTree;

添加单词“abz”，释义为“12345”；

图片助攻：

跟着代码走2遍：

//结构体定义typedef struct node{    int nFlag;    char* pStr;    struct node *pList[26];}TrieTree;

1.创建树

/*传入的数据： char* str[] = {
  "alibaba","aabb","lemon","windows","llleee"};char* str2[] = {
  "ali","a2b2","lemmon","wind", "l2e3"};*/

TrieTree* CreateTrieTree(char* str[], char* str2[], int nLength){    int i;    if( !str || !str2 || nLength <=0)        return NULL;    //1. 先来一个根节点    TrieTree* pRoot = (TrieTree*)malloc(sizeof(TrieTree));    memset(pRoot, 0, sizeof(TrieTree));    //添加单词和释义    for(i=0; i

2.添加单词 重点在这里！！！这能理解就大功告成了！

void Add(TrieTree*pTree, char* str, char* str2){    TrieTree* pTemp = NULL;    for( int i=0 ;i
   
    pList[str[i]-97] == NULL)        {            //添加新节点            pTemp = (TrieTree* )malloc(sizeof(TrieTree));            memset(pTemp, 0 , sizeof(TrieTree));            //这个字母的指针指向这个节点；            pTree->pList[str[i] - 97] = pTemp;        }        pTree = pTree->pList[str[i] - 97];    }    pTree->nFlag = 1;    pTree->pStr = str2;}
   

3.单词的查找

单词查找和创建差不多， 就是找到单词后，判断一下nFlag 是不是1，是1就找到了！如果找单词的过程中， 碰到了空节点那么说明没有这个单词！

void FindWord(TrieTree* pTree, const char* str){    if(!pTree)         return ;    while(*str)    {        if(pTree->pList[*str - 97] == NULL)        {            printf("not find\n");            return ;        }        pTree = pTree->pList[*str - 97];        str++;    }    if(pTree->nFlag)    {        printf("find: %s\n",pTree->pStr);    }    else    {        printf("not find\n");    }    return ;}

4.显示

//字典树就是一个26叉树， 类似二叉树的前序遍历，先打印根，再遍历26个孩子；void ShowAll(TrieTree* pRoot){    if(pRoot == NULL) return ;    if(pRoot->nFlag == 1)        printf("%s  \n" ,pRoot->pStr);    for(int i=0;i<26;i++)    {        ShowAll(pRoot->pList[i]);    }}

int main(){    char *str[] = {
  "alibaba","aabb","lemon","windows","llleee"};    char* str2[] = {
  "ali","a2b2","lemmon","wind", "l2e3"};    TrieTree* pTree = CreateTrieTree(str, str2, 5);    ShowAll(pTree);    FindWord(pTree, "alibaba");    FindWord(pTree, "aliba");}