字典树是一种树形结构，节点存储的不是完整的字符串而是前缀字符。
字典树的优点:因为通过前缀字符来选择树上的分支，所以可以节省时间
字典树的缺点:比较浪费空间，与总字符数量有关
字典树的根节点不存储字符。
用动态分配空间实现(常见)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef struct TreeNode {
int pass;//记录有多少个字符串以当前字符串做前缀
int end;//计入有多少个字符串以当前字符串结束
struct TreeNode* next[26];//指向下一个字符，即下一个节点
} Node;
typedef struct trie {//只需要知道根节点就可以访问整个字典树
Node* root;
} Trie;
void deleteNode(Node* root)//从root层序遍历字典树，删除root的整颗树，包括 root节点
{
if (root == NULL) {
return ;
}
Node* q[100000] = { 0 };//准备一个队列
int l = 0;//队列头
int r = 0;//队列尾
q[r++] = root;//根节点入队
while (l != r) {//只要队列中还有节点
Node* t = q[l++];//出队
for (int i = 0; i < 26; i++) {//访问所有孩子节点
if (t->next[i]) {//只要有孩子
q[r++] = t->next[i];//把孩子节点入队
}
}
free(t);//释放刚刚出队的节点，因为已经处理完了它的孩子节点，所以可以释放它了
}
}
void freeTrie(Trie* root) {
deleteNode(root -> root);//先释放字典树
free(root);//再释放root
}
Node* makeNode(void) {//创建一个节点
Node* node = (Node*)malloc(sizeof(Node));//malloc一个节点
node->end = 0;//初始化
node->pass = 0;//初始化
for (int i = 0; i < 26; i++) {
node->next[i] = NULL;//指向空代表没有路了
}
return node;//返回创建的节点
}
void insert(Trie* root, char s[]) {//把s放入字典树中
Node* r = root->root;//指向字典树的根节点
r->pass++;//先让根节点的pass加一，因为来到了根节点
for (int i = 0; s[i]; i++) {//遍历s中的每一个字符
int index = s[i] - 'a';//取出对应的下标，0 -> 'a' ~ 25 -> 'z'
if (r->next[index] == NULL) {//如果没有路了，那么就创建一个节点
r->next[index] = makeNode();//让对应的下标指向新创建的节点
}
r = r->next[index];//来到下一个节点
r->pass++;//因为来到一个新的节点，所以pass++
}
r->end++;//遍历完了之后，r来到最后一个节点，然后end++,表示以字符串s结尾的字符串的个数加一
}
int search(Trie* root, char s[]) {//返回在字典树中字符串s出现的次数
Node* cur = root->root;//指向字典树的根节点
for (int i = 0; s[i]; i++) {//遍历字符串中的每一个字符
int index = s[i] - 'a';//计算字符所对应的下标
if (cur->next[index] == NULL)//如果没有路了代表肯定没有这个字符串
{
return 0;//返回0，表示出现0次
}
cur = cur->next[index];//去下一个节点
}
return cur -> end;//最后返回最后一个节点的end，因为end表示以当前路径结尾组成的字符串有多少个
}
void deleteWord(Trie* root, char s[]) {//删除字典树中，字符串s，只删除一次
if (search(root, s)) {//只有存在字典树中才删除
Node* cur = root->root;//指向字典树的根节点
--cur->pass;//来到一个节点就让pass减一
for (int i = 0; s[i]; i++) {//遍历s中的每一个字符串
int index = s[i] - 'a';//取出对应的下标
//注意是下一个节点的 pass，因为要删掉的是下一个节点而不是当前的节点
if (--cur -> next[index] -> pass <= 0) {//如果下一个节点的pass减一之后 <= 0，那么释放下一个节点，因为后面的节点都没有用了。
deleteNode(cur->next[index]);//删除下一个节点的整颗树
cur->next[index] = NULL;//让它指向空
return;//没有必要再删了，因为已经删除完了，所以结束函数
}
cur = cur->next[index];//去对应的下一个节点
}
cur->end--;//让最后一个节点的end减一，表示字符串s在字典树中的出现次数减一
}
}
int prefixNumber(Trie* root, char s[]) {//返回在字典树中有多少个字符串以字符串s做前缀
Node* cur = root->root;//指向字典树的根节点
for (int i = 0; s[i]; i++) {//遍历字符串s的每一个字符
int index = s[i] - 'a';//取出对应的下标
if (cur->next[index] == NULL) {//如果没有路了代表字符串s没有在字典树中，那么就不可能有以s做前缀的字符串，所以返回0
return 0;
}
cur = cur->next[index];//去对应的下一个节点
}
return cur->pass;//pass含义就是以路径上的字符串做前缀的字符串个数
}
int main() {
int a;
int n;
char s[21] = "";
Trie* r = (Trie*)malloc(sizeof(Trie));
r->root = (Node*)malloc(sizeof(Node));
r->root->end = 0;
r->root->pass = 0;
for (int i = 0; i < 26; i++) {
r->root->next[i] = NULL;
}
scanf("%d", &n);
while (n--) {
scanf("%d %s", &a, &s);
if (a == 1) {
insert(r, s);
}
else if (a == 2) {
deleteWord(r, s);
}
else if (a == 3) {
if (search(r, s) > 0) {
printf("YES\n");
}
else {
printf("NO\n");
}
}
else {
int ans = prefixNumber(r, s);
printf("%d\n", ans);
}
}
freeTrie(r);
return 0;
}如果总字符类型很多的话，可以用哈希表做next数组来节约空间。
静态数组实现
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 150001
int tree[N][26] = {0};//N表示字典树最多同时有n个节点，根节点的下标是1
int end[N] = {0};//end数组表示以对应字符串的结尾的字符串的个数
int pass[N] = {0};//pass数组表示以对应字符串做前缀的字符串的个数
int cnt = 1;//表示使用到了多少下标，很关键的一个变量
void clear(void) {//从下标1到cnt的空间全部置为0
for (int i = 1; i <= cnt; i++) {
for (int j = 0; j < 26; j++) {
tree[i][j] = 0;
}
pass[i] = 0;
end[i] = 0;
}
}
void build(void) {//创建一个字典树就是让cnt等于1
cnt = 1;
}
void insert(char s[]) {//插入一个字符串s到字典树中
int cur = 1;//指向根节点的下标
pass[cur]++;//让根节点对应的pass++
for (int i = 0; s[i]; i++) {//遍历字符串s中的每一个字符
int index = s[i] - 'a';//取出对应的位置
if (!tree[cur][index]) {//如果tree[cur][index]的值为0，代表没有下一个节点，所以把++cnt的位置给它作为下一个节点
tree[cur][index] = ++cnt;
}
cur = tree[cur][index];//去下一个节点
pass[cur]++;//让对应的pass++
}
end[cur]++;//让对应的end++
}
int search(char s[]) {//返回字符串s在字典树中出现了多少次
int cur = 1;//来到根节点
for (int i = 0; s[i]; i++) {
int index = s[i] - 'a';
if (!tree[cur][index]) {//如果tree[cur][index]的值为0，代表没有路了，也就是在字典树中没有字符串s，所以返回0
return 0;
}
cur = tree[cur][index];//去下一个节点
}
return end[cur];//返回对应end，即字符串s在字典树中出现的次数
}
void deleteWord(char s[]) {//在字典树中删除字符串s
if (search(s) > 0) {//字符串s在字典树中出现过才删除
int cur = 1;//来到根节点
pass[cur]--;//根节点的pass值减一
for (int i = 0; s[i]; i++) {
int index = s[i] - 'a';
if (--pass[tree[cur][index]] <= 0) {//如果下一个节点对应的pass值减一后小于等于0了，那么代表这条分支没有用了，让对应的下标置为0
tree[cur][index] = 0;//为什么呢，因为cnt一直在加，没有减过，所以实际上是拿没有用过的空间来用，就像数组实现队列一样，队列尾一直往后面走。
return ;
}
cur = tree[cur][index];//去下一个节点
}
end[cur]--;//对应的end减一
}
}
int prefixNumber(char s[]) {//返回以字典树中以字符串s做前缀有多少个字符串
int cur = 1;
for (int i = 0; s[i]; i++) {
int index = s[i] - 'a';
if (!tree[cur][index]) {//如果tree[cur][index]的值为0，代表没有路了，也就是在字典树中没有字符串s
return 0;//所以返回0
}
cur = tree[cur][index];//去下一个节点
}
return pass[cur];//返回对应的pass值
}
int main(int argc, char* argv[])
{
int n;
char s[21] = "";
int t;
build();
sc("%d", &n);
while(n--) {
sc("%d %s", &t, s);
if (t == 1) {
insert(s);
}
else if (t == 2) {
deleteWord(s);
}
else if (t == 3) {
if (search(s) > 0) {
pr("YES\n");
}
else {
pr("NO\n");
}
}
else {
pr("%d\n", prefixNumber(s));
}
}
clear();
return 0;
}静态数组的实现本质是一种模拟链表,这样可以节约空间，因为实现了空间的复用，而且常数时间更快，所以写题目更推荐使用静态数组的实现。
标签：cur,trie,int,pass,字符串,root,节点,字典 From： https://www.cnblogs.com/lwj1239/p/17972273