trie树算法--c语言

1.什么是trie树

trie树，属于一种树，结构大概如下

假设我们输入几个字符串，adg，abc，ab，adhe，那么我们可以用这个树进行存储，带星号的表明这个字符串出现过，有相同前缀的那么会在一条路径上，比如adg和adhe，ad都是它们的前缀，所以在一条路径上，当出现不同的时候才会分开，我们通过树的形式将一个个节点连接起来（除了根节点不包含字符，其它每一个节点都包含一个字符）

2.trie树的作用

trie树可以用来检索某一个字符串是否出现过，我们通过查询操作来进行实现。

trie也可以统计某一个字符串出现过几次，也是通过查询操作来实现。

trie也可以进行前缀的统计，比如洛谷的这道题目。
trie还有许多其它的作用（我在这里就不列举了）。

3.trie树的基本操作实现

void insert(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
    int u = str[i] - 'a';
    if (!son[p][u]) son[p][u] = ++ idx;
    p = son[p][u];
}
cnt[p] ++ ;
}

这里son数组我们定义为son[题目的要求][26]，这里我们只是表示字母，不包含数字，所以有26个。

这是插入操作，str表示我们要插入的字符串，son则表示我们的trie树，idx则表示节点的个数，cnt数组表示这个字符串出现的次数（相当于做一个记号表示出现过），我们先将i当前指向的字符转换成数字编号，所以为str[i]-‘a’，之后我们进行判断，如果当前节点不存在那么我们就创造一个节点，如果存在的话那么我们就向下遍历，最后让cnt[p]++，表示这个字符串出现过一次。

int query(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
    int u = str[i] - 'a';
    if (!son[p][u]) return 0;
    p = son[p][u];
}
return cnt[p];
}

这是询问操作，返回这个字符串出现过几次，先初始化p为0，之后还是将字符转化成数字编号，之后进行查找，如果son[p][u]为0，那么表示没有这个节点，那么我们直接返回0表示没有找到，如果整个循环结束了那就表明我们找到了，就返回cnt[p]所对应的值就行了。