C++实现Trie字典树

69 阅读 0 评论 46 点赞

我是靠谱客的博主激情热狗，这篇文章主要介绍C++实现Trie字典树，现在分享给大家，希望可以做个参考。

一、前言

这篇文章来源于HihoCode的#1014题，此处为链接

二、Trie字典树

字典树，顾名思义就是将单词存在一个树结构中，用来对单词进行存储和查找功能，并且可以统计出以某一特定字符串为前缀共有多少单词，本文中只涉及英文单词。

字典树是一个26叉树，每一个父节点都有26个子节点，分别对应了26个英文字母，树的结构大致如下：

理所当然的根节点不代表任何字母，作为一个空节点。那么每个节点应当具有什么样的结构呢？

三、节点结构

节点中应当包含一个指向26个子节点的指针数组，为了统计以某一字符串为前缀的单词出现了多少次，节点中应当有此节点存储了多少次的计数值，并且应当存储下当前节点代表的字符。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
class TrieNode{
public:
int count;
TrieNode * nextNode[26];
char *word;
public:
TrieNode():word(NULL),count(0){
for(int i=0;i<26;i++){
nextNode[i]=NULL;
}
}
};

四、针对题目的分析

题目中要求先将给出的单词存入树中，这就要求我们的树需要有插入操作。插入操作可以通过递归和循环来实现，在这里我们介绍循环的方式。

每次插入一个单词时我们需要将对应的字符串的每一位提取出来，判断这个字符是否为合法的英文字符，并且在当前节点的子节点中找到这个字符对应的子节点。如果这个子节点不为空，说明之前已经插入过一次，那么这次插入只需要更新它的count计数，否则的话我们需要初始化这个节点，并且将它对应的字符和count计数值都更新。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void insert(string str){
int index;
TrieNode *tmp=root;
tmp->count++;
for(int i=0;i<str.size();i++){
index=str[i]-'a';
if(index < 0 || index > 25) return;
else if(tmp->nextNode[index]==NULL){
tmp->nextNode[index]=new TrieNode();
//tmp->nextNode[index]->word
}
tmp=tmp->nextNode[index];
tmp->count++;
tmp->word[0]=str[i];
}
}

当所有的单词都插入后，我们需要对给定的前缀出现的次数进行统计，也就是我们要找到这个前缀的最后一个字符所在的节点的count计数值。因此从根节点开始层层寻找，如果没有到这个前缀的字符的最后一位就遇到了空节点，说明字典中并没有存放这个前缀单词，需要返回零。如果找到了最后一个字符所在的节点，那么就返回它的计数值。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isFound(const string str,int & cnt){
int i=0;
int index=-1;
TrieNode *tmp=root;
for(;i<str.size();i++){
index=str[i]-'a';
if(0>index || index>25) {cnt=0;return false;}
tmp=tmp->nextNode[index];
if(tmp!=NULL) cnt=tmp->count;
else
{cnt=0;return false;}
}
return true;
}

这两个方法已经足够我们应付这道题目了，下面来介绍一下方便我们调试用的一个函数——打印整棵树。

打印整棵树其实就是遍历整棵树，我们为了方便就采取前序遍历，遍历采用简单的递归。

复制代码

1
2
3
4
5
6
7
8
9
10
11
void print(TrieNode * tmp){
if(tmp==NULL) return;
else{
cout<<tmp->word[0]<<"t";
}
for(int i=0;i<26;i++)
print(tmp->nextNode[i]);
}
void printAll(){
print(root);
}

五、完整代码

这里贴出完整的代码供大家参考。

复制代码

#include <iostream>
#include <string>
using namespace std;
class TrieNode{
public:
int count;
TrieNode * nextNode[26];
char *word;
public:
TrieNode():word(NULL),count(0){
for(int i=0;i<26;i++){
nextNode[i]=NULL;
}
}
};
class TrieTree{
public:
TrieNode * root;
TrieTree(){
root=new TrieNode();
}
~TrieTree(){
delete [] root;
}
void insert(string str){
int index;
TrieNode *tmp=root;
tmp->count++;
for(int i=0;i<str.size();i++){
index=str[i]-'a';
if(index < 0 || index > 25) return;
else if(tmp->nextNode[index]==NULL){
tmp->nextNode[index]=new TrieNode();
//tmp->nextNode[index]->word
}
tmp=tmp->nextNode[index];
tmp->count++;
tmp->word[0]=str[i];
}
}
bool isFound(const string str,int & cnt){
int i=0;
int index=-1;
TrieNode *tmp=root;
for(;i<str.size();i++){
index=str[i]-'a';
if(0>index || index>25) {cnt=0;return false;}
tmp=tmp->nextNode[index];
if(tmp!=NULL) cnt=tmp->count;
else
{cnt=0;return false;}
}
return true;
}
void print(TrieNode * tmp){
if(tmp==NULL) return;
else{
cout<<tmp->word[0]<<"t";
}
for(int i=0;i<26;i++)
print(tmp->nextNode[i]);
}
void printAll(){
print(root);
}
};
int N;
int S;
int main(){
TrieTree t;
int cnt=0;
string str;
cin>>N;
int i;
int *a;
for(i=0;i<N;i++){
cin>>str;
//cout<<"hi"<<endl;
t.insert(str);
}
t.printAll();
cin>>S;
a=new int[S];
for(i=0;i<S;i++){
cnt=0;
cin>>str;
t.isFound(str,cnt);
a[i]=cnt;
}
for(i=0;i<S;i++){
cout<<a[i]<<endl;
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <string>
using namespace std;
class TrieNode{
public:
int count;
TrieNode * nextNode[26];
char *word;
public:
TrieNode():word(NULL),count(0){
for(int i=0;i<26;i++){
nextNode[i]=NULL;
}
}
};
class TrieTree{
public:
TrieNode * root;
TrieTree(){
root=new TrieNode();
}
~TrieTree(){
delete [] root;
}
void insert(string str){
int index;
TrieNode *tmp=root;
tmp->count++;
for(int i=0;i<str.size();i++){
index=str[i]-'a';
if(index < 0 || index > 25) return;
else if(tmp->nextNode[index]==NULL){
tmp->nextNode[index]=new TrieNode();
//tmp->nextNode[index]->word
}
tmp=tmp->nextNode[index];
tmp->count++;
tmp->word[0]=str[i];
}
}
bool isFound(const string str,int & cnt){
int i=0;
int index=-1;
TrieNode *tmp=root;
for(;i<str.size();i++){
index=str[i]-'a';
if(0>index || index>25) {cnt=0;return false;}
tmp=tmp->nextNode[index];
if(tmp!=NULL) cnt=tmp->count;
else
{cnt=0;return false;}
}
return true;
}
void print(TrieNode * tmp){
if(tmp==NULL) return;
else{
cout<<tmp->word[0]<<"t";
}
for(int i=0;i<26;i++)
print(tmp->nextNode[i]);
}
void printAll(){
print(root);
}
};
int N;
int S;
int main(){
TrieTree t;
int cnt=0;
string str;
cin>>N;
int i;
int *a;
for(i=0;i<N;i++){
cin>>str;
//cout<<"hi"<<endl;
t.insert(str);
}
t.printAll();
cin>>S;
a=new int[S];
for(i=0;i<S;i++){
cnt=0;
cin>>str;
t.isFound(str,cnt);
a[i]=cnt;
}
for(i=0;i<S;i++){
cout<<a[i]<<endl;
}
return 0;
}