C++实现Trie字典树

一、前言

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

二、Trie字典树

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

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

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

三、节点结构

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

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计数值都更新。

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);
}

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

#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;
}

最后

以上就是激情热狗为你收集整理的C++实现Trie字典树的全部内容，希望文章能够帮你解决C++实现Trie字典树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。