简述字典树

编程入门行业动态更新时间:2024-10-28 07:26:17

简述<a href=https://www.elefans.com/category/jswz/34/1770269.html style= 字典树"/>

简述字典树

字典树主要用于字符串的存储与查询，其与哈希存储相比，具有近乎相同的时间效率和较高的空间效率，关键是字典树能完成一些用哈希很难解决又有较高时间要求的问题。

举例

假设给定我们一些小写英文字符构成的字符串，要求给一个前缀，能快速返回这组单词中拥有该前缀的数量。

比如“brad”，“bread”，“bed”，“bedroom”，“bedding”这五个字符串，快速查找最好的办法就是用哈希了，时间复杂度为O(1)。但是查找具有相同前缀单词的数量，这个用哈希似乎并不能很好解决，下面我们看下字典树是如何处理的。

树是由一个个节点构成的，先来看下字典树节点的定义：

typedef struct node{int val;                               //用于记录有多少个单词以此为前缀，节点每被访问一次，其下val值自增1次struct node *next[26];                 //26个指针，0给a，1给b，以此类推
}node;

因为字符串是小写英文字符，所以每个节点下均有26个指针，其指向的是下一个字符。而val域一般用于做标记，每个程序里起到不同的作用，在这里主要用于记录有多少个单词以此为前缀。

一. 如何构建字典树？

1. 首先新建字典树的根节点root，其的子节点均为空；为防止野指针，子节点指针全部指向空，如图一。

2. 插入brad
获取brad的首字母b，因为root下没有任何节点，所以新建root的子节点b。
获取brad的第二个字母r，再因为节点b刚刚建立，所以其下没有任何节点，故新建节点b的子节点r。
获取brad的第三个字母a，刚刚新建的节点r下没有任何子节点，所以新建节点r的子节点a。
获取brad的最后一个字母d，节点a下没有任何新节点，故再新建节点a的子节点d。
所有新建节点的val值均为1，至此brad已经插入完成，字典树如图二所示。

3. 插入bread
获取bread的首字母b，准备将节点b插到root下，由于之前brad插入时已在root下开辟了b节点，所以不需要再新建b节点，拿来用即可。同时将b节点的val自增1次，即val=2。
获取bread的第二个字母r，再次发现节点b下已经有了节点r，故不再新建节点r，直接使用即可。同时将节点r的val自增1次，即val=2。
获取bread的第三个字母e，由于r节点下只有a节点并没有节点e，所以需要新建r的子节点e。
获取bread的第四个字母a，由于刚刚新建的节点e下没有任何子节点，故新建e的子节点a。
获取bread最后一个字母d，同理在刚刚建立的节点a下新建子节点d。
所有新建节点的val值均为1，bread插入完成后，字典树如图三所示。

4. 接着再分别插入bed、bedroom、bedding单词，插入后字典树分别如图四、图五、图六所示。

注意： 如果没有定义val域，那么在插入单词bedroom时，之前的bed就被bedroom覆盖了；最终我们也不知道有bed这个单词，所以节点中必定有个域来做记录。这里由于我们最终是返回是前缀的数量，所以val需要不停的自增。在另外的题目中，val就可能会是其他的作用。

二. 如何求以某前缀开头的单词数量？

思路和插入是一样的，只是如果没有在树中找到对应的节点，不再是新建对应的节点，而是结束返回0，表明无此前缀。

另种情况是前缀中所有字母按序获取完成后，这时只需返回当前节点的val即可。

求以bed为前缀的单词数量：

获取bed的首字母b，在root的子节点中发现有b节点。

获取bed的第二个字母e，同样在b节点下发现存在子节点e。

获取bed的第三个字母d，节点e下同样有子节点d。

至此bed已经全部获取，返回字典树中所处节点的val值，从图中可以知道节点d的值为3，即有3个以bed作为前缀的单词。

从图中还可得到：从根节点到某节点，路径上经过的字符连接起来，即为该节点所对应的字符串。

代码实现

#include<stdio.h>
#include<stdlib.h>typedef struct node{int val;                               //用于记录有多少个单词以此为前缀，节点每被访问一次，其下val值自增1次struct node *next[26];                 //26个指针，0给a，1给b，以此类推
}node;node* newnode()                            //构造字典树的新节点，函数返回该节点的地址
{node* root=(node*)malloc(sizeof(node));//动态开辟内存for(int i=0;i<26;i++)                  //新构造节点的子节点指针全为NULL{root->next[i]=NULL;}root->val=0;return root;
}void insert(node *root,char *s)            //传入字典树根节点和待插入的字符串s
{for(int i=0;s[i]!='\0';i++)            //遍历字符串s{if(root->next[s[i]-'a']==NULL)     //如果节点s[i]不存在则新建{root->next[s[i]-'a']=newnode();}root=root->next[s[i]-'a'];         //更新指针指向root->val++;                       //节点val值自增1次表明多1个以该前缀的单词}
}int search(node *root,char *s)             //传入字典树根节点和待搜索的字符串s
{for(int i=0;s[i]!='\0';i++)            //遍历待搜索字符串{if(root->next[s[i]-'a'])root=root->next[s[i]-'a'];elsereturn 0;                      //未找到则返回0}return root->val;                      //遍历结束，返回数量
}void release(node *root)                   //释放字典树
{for(int i=0;i<26;i++)                  //遍历该节点下的26个子节点{if(root->next[i])                  //存在节点{release(root->next[i]);        //递归释放}}free(root);                            //释放
}int main()
{node *root=newnode();                  //构建字典树根节点insert(root,"brad");insert(root,"bread");insert(root,"bed");insert(root,"bedroom");insert(root,"bedding");printf("%d\n",search(root,"bed"));printf("%d\n",search(root,"br"));printf("%d\n",search(root,"b"));release(root);return 0;
}

运行结果：