字典树（模板）

本是古典何须时尚 2021-12-10 07:37 251阅读 0赞

Trie树（来自单词retrieval），又称前缀字，单词查找树，字典树，是一种树形结构，是一种哈希树的变种，是一种用于快速检索的多叉树结构。

字典树是处理字符串常见的一种树形数据结构，其优点是利用字符串的公共前缀来节约存储空间

字典树完整结构

![1468919-20190712194222402-1818601161.png][]

**实际上每个节点的子节点都应该从0编到——25，但这样会发现许多事根本用不到的。比如上图的根节点应该分出26个叉。节约空间，用到哪个分哪个。**

字典树建树：

![1468919-20190712194509769-823522062.png][]

字典树理解

![1468919-20190712194705915-203870729.png][]

模板：

一、建树

void insert()//插入单词s
    {
        len=strlen(s);//单词s的长度
        root=0;//根节点编号为0
        for(int i=0;i<len;i++)
        {
            int id=s[i]-'a';//第二种编号
            if(!trie[root][id])//如果之前没有从root到id的前缀 
                        trie[root][id]=++tot;//插入，tot即为第一种编号
            root=trie[root][id];//顺着字典树往下走
        }
    }

注意：编号的时候，若tot初始为0，编号要++tot;若初始为1，可以tot++

二、查找

bool search()
    {
        len=strlen(s);
        root=0;//从根结点开始找
        for(int i=0;s[i];i++)
        {
            int x=s[i]-'a';//
            if(trie[root][x]==0)   return false;//以root为头结点的x字母不存在，返回0 
            root=trie[root][x];//为查询下个字母做准备，往下走 
        }
        return true;//找到了
    }

应用：

字典树建树的过程在不同的应用场景基本上没有变化，字典树的查找部分是最主要的操作，在不同的应用场景，只要对search部分变化即可

1、如果是**查询某个单词**的话，我们用bool变量 v\[i\]表示节点i是否是单词结束的标志。

那么最后return的是v\[root\],所以在插入操作中插入完每个单词是，要对单词最后一个字母的v\[i\]置为true，其他的都是false

2、如果是查询**前缀出现的次**数的话，那就在开一个sum\[\]，表示位置i被访问过的次数，

那么最后return的是sum\[root\]，插入操作中每访问一个节点，都要让他的sum++

这里前缀的次数是标记在前缀的最后一个字母所在位置的后一个位置上。

比如:前缀abc出现的次数标记在c所在位置的后一个位置上，

![1468919-20190712195251513-1146724195.png][]

[转载自https://www.cnblogs.com/TheRoadToTheGold/p/6290732.html][https_www.cnblogs.com_TheRoadToTheGold_p_6290732.html]

转载于:https://www.cnblogs.com/-citywall123/p/11178106.html

[1468919-20190712194222402-1818601161.png]: /images/20211210/08d22dd567a244c095799ab045922afc.png
[1468919-20190712194509769-823522062.png]: /images/20211210/5a6eadd02ed6427abd5625fe4d367608.png
[1468919-20190712194705915-203870729.png]: /images/20211210/dfa85c2134974fa9b6ca5126377bba3e.png
[1468919-20190712195251513-1146724195.png]: /images/20211210/48a30541f4a84ff3a2a329276101b1c9.png
[https_www.cnblogs.com_TheRoadToTheGold_p_6290732.html]: https://www.cnblogs.com/TheRoadToTheGold/p/6290732.html