字典树入门详解+一道入门水题

朴灿烈づ我的快乐病毒、 2022-06-10 02:22 150阅读 0赞

## **字典树** ##

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

![这里写图片描述][SouthEast]

字典树的结构定义：

typedef struct node{
        node *next[26];
        int cnt;
        node(){
            cnt=0;
            memset(next,0,sizeof(next));
        }
    };
    node *root=NULL;

（注：next 是表示每层有多少种类的数，如果只是小写字母，则26即可，若改为大小写字母，则是52，若再加上数字，则是62了，这里根据题意来确定；cnt 可以表示一个字典树到此有多少相同前缀的数目，这里根据需要应当学会自由变化。）

字典树基本操作有：查找、插入和删除,当然删除操作比较少见（这个主要用于大量数据时，防止MLE）。

实现方法：  
搜索字典项目的方法为：  
(1) 从根结点开始一次搜索；  
(2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；  
(3) 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。  
(4) 迭代过程……  
(5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。  
其他操作类似处理

下面给出建树和查找与删除的模板：

//建树（每输入一次，更新一次树）
    void buidTree(char *s){
        node *p=root;
        node *tmp=NULL;
        int l=strlen(s);
        for(int i=0;i<l;i++){
            if(p->next[s[i]-'a']==NULL){
       //如果当前结点层没有出现过这个元素，则新声明一个node
                tmp=new node;
                p->next[s[i]-'a']=tmp;
            }
            p=p->next[s[i]-'a'];//逐层建树
            p->cnt++;//每经过一次，前缀数量+1
        }
    }
    //查找
    void findTree(char *s){
        node *p=root;
        int l=strlen(s);
        for(int i=0;i<l;i++){
            if(p->next[s[i]-'a']==NULL){
       //查找失败，返回0
                printf("0\n");
                return;
            }
           p=p->next[s[i]-'a'];//逐层查询
        }
        printf("%d\n",p->cnt);
    }
    删除
    void del(node *root){
        for(int i=0;i<0;i++){
            if(root->next[i]){
                del(root->next[i]);
            }
        }
        delete(root);
    }

下面附上一道水题（裸字典树），方便新手入门：  
[HDU1251 统计难题][HDU1251]

下面是AC代码

#include <iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    typedef struct node{
        node *next[26];
        int cnt;
        node(){
            cnt=0;
            memset(next,0,sizeof(next));
        }
    };
    node *root=NULL;
    //建树
    void buidTree(char *s){
        node *p=root;
        node *tmp=NULL;
        int l=strlen(s);
        for(int i=0;i<l;i++){
            if(p->next[s[i]-'a']==NULL){
                tmp=new node;
                p->next[s[i]-'a']=tmp;
            }
            p=p->next[s[i]-'a'];
            p->cnt++;
        }
    }
    //查找
    void findTree(char *s){
        node *p=root;
        int l=strlen(s);
        for(int i=0;i<l;i++){
            if(p->next[s[i]-'a']==NULL){
                printf("0\n");
                return;
            }
           p=p->next[s[i]-'a'];
        }
        printf("%d\n",p->cnt);
    }
    删除
    void del(node *root){
        for(int i=0;i<0;i++){
            if(root->next[i]){
                del(root->next[i]);
            }
        }
        delete(root);
    }
    int main()
    {
        char s[25];
        root=new node;
        while(gets(s)){
            if(strcmp(s,"")==0)
                break;
            buidTree(s);
        }
        while(scanf("%s",&s)!=EOF){
            findTree(s);
        }
        del(root);
        return 0;
    }

[SouthEast]: /images/20220610/cd08907da4b24dcfa8b66d40d8761675.png
[HDU1251]: http://acm.hdu.edu.cn/showproblem.php?pid=1251