??Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
给定如下单词：abc、abd、cbd、ccce、bcda、ccc
Tire树的结构大致如下：
那它是如何构造的呢？
?? 首先从根节点开始我们要存放单词abc，判断根节点是否有存放着字母 a 的子节点，如果没有就增加一个节点将a存进去；接着在 a 节点判断 a 节点是否有存放字母 b 的子节点，同样的没有就新增一个节点用来存放 b ，c也同理。
??接下来存放abd，存放完一个单词后指针要回到根节点重新移动。字母 a 显然已经有了，指针直接移到该节点；接着看 b ，也有了继续移动；存放字母 d 的时候发现b节点没有子节点存放d那就新增一个存放字母d，这样第二个单词也存放完成了。
??那我们查找的时候怎么知道单词的结束位置呢？很简单在存放的时候，当存放结束时将最后一个节点做标记即可，同个这样标记我们还可以非常快速的得到一个单词总共出现了几次。
接下来看一个题目巩固一下：https://www.acwing.com/problem/content/837/
??题目目的很明确就是要将单词插入然后询问某些单词出现了几次：
??代码实现方面一般可以用 指针链表的形式实现，我偷个懒用数组模拟指针实现了：
#include<iostream>
using namespace std;
const int N = 100007;
int Tire[N][26];
int cnt[N], index;//cnt数组用来标记单词的结尾，存放出现的次数，index用来模拟指针
char s[N];
void insert(char str[]) {//插入操作
int p = 0;
for (int i = 0; str[i]; i++) {
int id = str[i] - 'a';
if (!Tire[p][id]) {//如果没有这个节点就增加
Tire[p][id] = ++index;
}
p = Tire[p][id];
}
cnt[p]++;
}
int Query(char str[]) {//查询操作
int p = 0;
for (int i = 0; str[i]; i++) {
int id = str[i] - 'a';
if (!Tire[p][id]) return 0;
p = Tire[p][id];
}
return cnt[p];//返回出现的次数
}
int main() {
int n;
cin >> n;
while (n--) {
char op[2];
cin >> op >> s;
if (op[0] == 'I') insert(s);
else cout << Query(s) << '\n';
}
return 0;
}
可以尝试用指针实现以下。
下面又是一道变形题：https://www.acwing.com/problem/content/description/145/
直接贴代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int Tire[N * 31][2], cnt[N * 31];
int id = 0;
void insert(int x) {//插入一个数
int p = 0;
for (int i = 30; i >= 0; i--) {
int t = (x >> i) & 1;//获得第i + 1位的二进制位
if (!Tire[p][t]) Tire[p][t] = ++id;//没有就开一个新节点
p = Tire[p][t];
}
cnt[p]++;//结尾标记
}
int Query(int x) {
int p = 0;
int res = 0;
for (int i = 30; i >= 0; i--) {
//从高位开始找
int t = (x >> i) & 1;
//如果这个数字的第i + 1 位相反的二进制位存在（!t）就取出来 否则按照x走
if (Tire[p][!t]) t = !t;
res = (res << 1) + t;
p = Tire[p][t];
}
return res^x;
}
int main() {
int n, x;
int maxAns = 0;
cin >> n;
while (n--) {
cin >> x;
insert(x);
maxAns = max(maxAns, Query(x));
}
cout << maxAns;
return 0;
}