Introduction

Trie树用来存储字符串，并且字符串的组成单元有范围。例如全部都是小写字母，全部都是大写字母，全部都是数字之类的情况。

Train of Thought

实际上是树状结构，每个节点下分出多个节点。对于每个节点，我们用idx变量赋予其一个地址。然后使用son[][]二维数组来进行索引，记录每个节点下面的节点的地址：一维下标为爹节点，二维下标为子节点，并且二维下标为从0到25，因为只有26个字母。

数组下标：表示每个节点的位置。0有两种含义：根节点、空节点。

对于每个节点，都有一个cnt参数，用来存储终点为该节点的字符串的个数

插入一个字符串

void Insert(char *str) {
    int p = 0;
    // 表示从根节点开始查询并插入
    for (int i = 0; str[i]; i ++ ) {
        int u = str[i] - 'a';
        // 把字符变成0到26的整数
        if (!son[p][u]) son[p][u] = ++ idx;
        // 表示p节点的，下标为u的，子节点
        // 如果不存在这个节点，就新建一个；如果存在则不做改变
        p = son[p][u];
        // 指针移动到下一个节点
    }
    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;
        // 如果往下找不到，则说明不存在欲查询的字符串，直接返回0
        p = son[p][u];
    }
    return cnt[p];
}