Trie树

Trie树(字典树)

Trie树，是使用树形结构来存储字符串的一种方式，由于使用了树形结构，大大加快了字符串的存储以及多次查询的速度。
Trie树一般用于多字符串存储 ， 以及查询一个字符串的出现次数时使用，或者查询以某段字符为前缀的字符串也可。

关于trie树的构造以及树形图像，请看这篇博客
Trie树(前缀树、字典树)

这里仅给出了代码实现。同时树形结构的建立使用静态数组模拟。

相关参数定义如下

#define root 0//规定节点0为根节点，不存储任何关系
const int N = 1e6 + 20;
int son[N][26], cnt[N], idx;
//son数组是树形结构数组。其第一维代表着一个节点，而第二维度来表征节点之间的关系
//比如son[0][0] = 1 代表着根节点有一个孩子节点，其中存储的值为'a',其所位于的位置为编号为1的节点。
//而cnt数组用于标记字符串结尾。当该节点为所插入字符串的最后一个字符时，cnt[该节点]++，即以该节点结尾的字符串数量加1
//idx永远指向下一个未使用的节点索引，用于扩展节点时用
//这里规定当节点值为0时为空节点

向trie树中插入一个字符串的操作如下

void insert(string str)
{
	int p = root;//从根节点开始找
	for (int i = 0; i < str.size(); i++)
	{
		int u = str[i] - 'a';//将ascill码转换为索引值(0-25 对应 a - z)
		if (!son[p][u]) son[p][u] = ++idx; //若该节点没有索引为u的孩子节点，则创建该节点
		p = son[p][u];//继续向下查找
	}
	cnt[p]++;//插入结束，将以最后节点为结尾的字符串数量++
}

从trie树中查询目标字符串个数操作如下

int query(string str)
{
	int p = root;//依旧从根节点开始查找
	for (int i = 0; i < str.size(); i++)
	{
		int u = str[i] - 'a';
		if (!son[p][u]) return 0;//有一位字符没有找到，即可确定trie树中未存储该字符，直接返回该字符串数量为0
		p = son[p][u];//若能找到，就继续
	}
	return cnt[p];//返回以最后一个节点为结尾的字符串数量
}