字典树(前缀树)_字典树java实现

大家好，又见面了，我是你们的朋友全栈君。

什么是字典树？

• 叫前缀树更容易理解
• 字典树的样子

这里写图片描述

Trie又被称为前缀树、字典树，所以当然是一棵树。上面这棵Trie树包含的字符串集合是{in, inn, int, tea, ten, to}。每个节点的编号是我们为了描述方便加上去的。树中的每一条边上都标识有一个字符。这些字符可以是任意一个字符集中的字符。比如对于都是小写字母的字符串，字符集就是’a’-‘z’；对于都是数字的字符串，字符集就是’0’-‘9’；对于二进制字符串，字符集就是0和1。

比如上图中3号节点对应的路径0123上的字符串是inn，8号节点对应的路径0568上的字符串是ten。终结点与集合中的字符串是一一对应的。

原理

下面我们来讲一下对于给定的字符串集合{W1, W2, W3, … WN}如何创建对应的Trie树。其实上Trie树的创建是从只有根节点开始，通过依次将W1, W2, W3, … WN插入Trie中实现的。所以关键就是之前提到的Trie的插入操作。 具体来说，Trie一般支持两个操作： 1. Trie.insert(W)：第一个操作是插入操作，就是将一个字符串W加入到集合中。 2. Trie.search(S)：第二个操作是查询操作，就是查询一个字符串S是不是在集合中。

假设我们要插入字符串”in”。我们一开始位于根，也就是0号节点，我们用P=0表示。我们先看P是不是有一条标识着i的连向子节点的边。没有这条边，于是我们就新建一个节点，也就是1号节点，然后把1号节点设置为P也就是0号节点的子节点，并且将边标识为i。最后我们移动到1号节点，也就是令P=1。

这里写图片描述

这样我们就把”in”的i字符插入到Trie中了。然后我们再插入字符n，也是先找P也就是1号节点有没有标记为n的边。还是没有，于是再新建一个节点2，设置为P也就是1号节点的子节点，并且把边标识为n。最后再移动到P=2。这样我们就把n也插入了。由于n是”in”的最后一个字符，所以我们还需要将P=2这个节点标记为终结点。

这里写图片描述

现在我们再插入字符串”inn”。过程也是一样的，从P=0开始找标识为i的边，这次找到1号节点。于是我们就不用创建新节点了，直接移动到1号节点，也就是令P=1。再插入字符n，也是有2号节点存在，所以移动到2号节点，P=2。最后再插入字符n这时P没有标识为n的边了，所以新建3号节点作为2号节点的子节点，边标识为n，同时将3号节点标记为终结点：

这里写图片描述

将后面的字符串int tea ten to都插入之后，就得到了我们一开始给出的Trie：

这里写图片描述

综上所述，在Trie中插入一个字符串W的伪代码如下：

这里写图片描述

下面我们再讲一下如何查询Trie树中是不是包含字符串S，也就是之前提到的查找操作。查找其实比较简单。我们只要从根节点开始，沿着标识着S[1] -> S[2] -> S[3] … -> S[S.len]的边移动，如果最后成功到达一个终结点，就说明S在Trie树中；如果最后无路可走，或者到达一个不是终结点的节点，就说明S不在Trie树中。

这里写图片描述

如果是查找”te”，就会从0开始经过5最后到达6。但是6不是终结点，所以te没在Trie树中。如果查找的是”too”，就会从0开始经过5和9，然后发现之后无路可走：9号节点没有标记为o的边连出去。所以too也不在Trie中。

综上所述，在Trie树中查找一个字符串的伪代码如下：

这里写图片描述

代码实现

数组方式实现 要写代码实现一个Trie首先就要确定如何存储一个Trie结构。这里用一个二维数组来存储：

int trie[MAX_NODE][CHARSET]; int k; 其中MAX_NODE是trie中最大能存储的节点数目，CHARSET是字符集的大小，k是当前trie中包含有多少个节点。Trie[i][j]的值是0表示trie树中i号节点，并没有一条连出去的边，满足边上的字符标识是字符集中第j个字符（从0开始）；trie[i][j]的值是正整数x表示trie树中i号节点，有一条连出去的边，满足边上的字符标识是字符集中第j个字符，并且这条边的终点是x号节点。

• 简单实现

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int MAX_NODE = 1000000 + 10;
const int CHARSET = 26;
int trie[MAX_NODE][CHARSET] = {
0};
int color[MAX_NODE] = {
0};
int k = 1;
void insert(char *w){
int len = strlen(w);
int p = 0;
for(int i=0; i<len; i++){
int c = w[i] - 'a';
if(!trie[p][c]){
trie[p][c] = k;
k++;
}
p = trie[p][c];
}
color[p] = 1;
}
int search(char *s){
int len = strlen(s);
int p = 0;
for(int i=0; i<len; i++){
int c = s[i] - 'a';
if(!trie[p][c]) return 0;
p = trie[p][c];
}
return color[p] == 1;
}
int main(){
int t,q;
char s[20];
scanf("%d%d", &t,&q);
while(t--){
scanf("%s", s);
insert(s);
}
while(q--){
scanf("%s", s);
if(search(s)) printf("YES\n");
else printf("NO\n");
}
return 0;
}

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/196234.html原文链接：https://javaforall.cn