Trie详解

article/2025/9/22 1:24:18

Trie，又名字典树、单词查找树，可以较高效地实现统计、排序和保存大量的字符串。

顾名思义，Trie是一个树状的结构，按照树型结构来存储字符串，显然是一种以空间换时间的方法。整体上理解和实现都不会很难。

下面是实现方法：

插入：

当我们往一棵Trie中插入一个字符串时，我们先定义一个指针p指向根节点，然后依次扫描字符串的元素，设其为s；
若s字符指向的是一个已存在的节点，设其为q，则令p=q；若s字符指向的一个是空节点，则新建一个节点，设其为q，并令p=q；
按照上面的步骤将字符串的元素扫描完毕后，将当前的p标记为一个字符串的末尾。

代码：

int p=0;
for(int i=0;i<s.size();i++)
{if(!trie[p][s[i]-'a'])trie[p][s[i]-'a']=++tot;//指向新节点p=trie[p][s[i]-'a'];//取出指针
}
end[p]=true;

查找：

当我们要在一颗Trie中查找一个字符串是否存在时，我们先定义一个指针p指向根节点，然后依次扫描字符串的元素，设其为s；
若s字符指向的是一个空节点，则说明s没有被插入过这棵Trie；若s字符指向的是一个已存在的节点，设其为q，则令p=q；
按照上面的步骤将字符串的元素扫描完毕后，若当前的p为一个字符串的末尾，则该字符串存在于这棵Trie中；反之则不存在。

代码：

int p=0;
for(int i=0;i<s.size();i++)
{p=trie[p][s[i]-'a'];//取出指针if(!p)return 0;
}
return end[p]；

它大概长这样：（来自lyd的蓝书）

完整代码：

#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int n,m,tot=1,trie[SIZE][26];//trie数组存的就是指针
bool end[SIZE];//SIZE表示所有字符串的长度之和
string s;
void add()
{int p=0;for(int i=0;i<s.size();i++){if(!trie[p][s[i]-'a'])trie[p][s[i]-'a']=++tot;p=trie[p][s[i]-'a'];}end[p]=true;
}
int get()
{int p=0;for(int i=0;i<s.size();i++){p=trie[p][s[i]-'a'];if(!p)return 0;}return end[p];
}
int main()
{memset(end,false,sizeof(end));cin>>n;for(int i=1;i<=n;i++){cin>>s;add();}cin>>m;for(int i=1;i<=m;i++){cin>>s;int ans=get();if(ans)cout<<"OK"<<endl;elsecout<<"WRONG"<<endl;}return 0;
}

（注：以上代码中字符串默认为只由小写字母构成，有的部分要根据实际情况改变）

习题：