title: Trie树之C++实现
comments: true
date: 2016-10-02 16:59:54
categories: 算法
tags:
- Trie树
前言
之前写了一篇偏向于理解Trie的文章－Trie树理解
和前面那篇文章不同的是，这一篇文章记录着Trie树的C++实现；
介绍
看一下代码的结构
其中：
- TrieNode : 树的结点，树
- Client : 客户端（操作树）
- main : 主函数
Code
TrieNode
TrieNode.hpp
//
// TreeNode.hpp
// Trie
//
// Created by staff on 16/9/29.
// Copyright © 2016年 staff. All rights reserved.
//
#ifndef TreeNode_hpp
#define TreeNode_hpp
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <stack>
using namespace std;
#define MAX_CHARS 26
class TreeNode {
public:
TreeNode();
~TreeNode();
void setEnd(bool);
bool getEnd();
void setFreq(int);
int getFreq();
void setNChar(char);
char getNChar();
void setID(int);
int getID();
void setStr(string);
string getStr();
vector<TreeNode *> Childs;
private:
bool End;
int Freq;
char NChar;
int Id;
string str;
};
class Tree {
public:
Tree();
~Tree();
void addTrieNode(string word, int id);
void deleteTrieNode();
map<int, string> searchTrie(string word);
void upateTree(string word, int id);
int getWordFreq(string word);
private:
TreeNode * root;
void addTrieNode(TreeNode * node, string word, int id);
void deleteTrieNode(TreeNode * root);
map<int, string> searchTrie(TreeNode * root, string word);
int getPrefixCount(TreeNode * root, string word);
void upateTree(TreeNode * root, string word, int id);
int getWordFreq(TreeNode * root, string word);
};
#endif /* TreeNode_hpp */
TreeNode.cpp
//
// TreeNode.cpp
// Trie
//
// Created by staff on 16/9/29.
// Copyright © 2016年 staff. All rights reserved.
//
#include "TreeNode.hpp"
TreeNode::TreeNode() : End(false), Freq(0), NChar(' '), str("") {
for (int i = 0; i < MAX_CHARS; ++i) {
this->Childs.push_back(nullptr);
}
}
TreeNode::~TreeNode() {
for (auto itr = this->Childs.begin(); itr != this->Childs.end(); itr++) {
delete *itr;
*itr = nullptr;
}
this->Childs.clear();
}
void TreeNode::setEnd(bool value) {
this->End = value;
}
bool TreeNode::getEnd() {
return this->End;
}
void TreeNode::setFreq(int value) {
this->Freq = value;
}
int TreeNode::getFreq() {
return this->Freq;
}
void TreeNode::setNChar(char value) {
this->NChar = value;
}
char TreeNode::getNChar() {
return this->NChar;
}
void TreeNode::setID(int value) {
this->Id = value;
}
int TreeNode::getID() {
return this->Id;
}
void TreeNode::setStr(string value) {
this->str = value;
}
string TreeNode::getStr() {
return this->str;
}
Tree::Tree() {
this->root = new TreeNode();
}
Tree::~Tree() {
}
void Tree::addTrieNode(TreeNode * root, string word, int id) {
if (word.size() == 0) {
return ;
}
TreeNode * pNode = root;
for (int i = 0; i < word.size(); ++i) {
int idx = word[i] - 'a';
if (pNode->Childs[idx] == nullptr) {
pNode->Childs[idx] = new TreeNode();
}
pNode->Childs[idx]->setNChar(word[i]);
pNode->Childs[idx]->setStr(pNode->getStr() + pNode->Childs[idx]->getNChar());
pNode = pNode->Childs[idx];
}
pNode->setID(id);
pNode->setFreq(pNode->getFreq()+1);
pNode->setEnd(true);
}
void Tree::deleteTrieNode(TreeNode * root) {
TreeNode * node = root;
for (int i = 0; i < MAX_CHARS; ++i) {
if (node->Childs[i]) {
deleteTrieNode(node->Childs[i]);
}
}
delete(node);
node = nullptr;
}
map<int, string> Tree::searchTrie(TreeNode * root, string word) {
if (word.size() == 0) {
return {};
}
map<int, string> result;
TreeNode * pNode = root;
int i = 0;
for (; i < word.size(); ++i) {
int idx = word[i] - 'a';
if (pNode->Childs[idx] == nullptr) {
break;
}
pNode = pNode->Childs[idx];
}
if (i != word.size()) {
cout << "not exist!" << endl;
return {};
}
else {
result.insert(make_pair(pNode->getID(), pNode->getStr()));
stack<TreeNode *> stack;
stack.push(pNode);
while (!stack.empty()) {
TreeNode * node = stack.top();
stack.pop();
for (int j = 0; j < MAX_CHARS; ++j) {
if (node->Childs[j]) {
if (node->Childs[j]->getEnd()) {
result.insert(make_pair(node->Childs[j]->getID(), node->Childs[j]->getStr()));
}
else {
stack.push(node->Childs[j]);
}
}
}
}
return result;
}
}
/**
* 词频统计，出现字符串的个数
*
* @param root <#root description#>
* @param word <#word description#>
*
* @return <#return value description#>
*/
int Tree::getWordFreq(TreeNode * root, string word) {
TreeNode * pNode = root;
int i = 0;
for (; i < word.size(); ++i) {
int idx = word[i] - 'a';
if (pNode->Childs[idx] == nullptr) {
return 0;
}
pNode = pNode->Childs[idx];
}
return pNode->getFreq();
}
void Tree::upateTree(TreeNode * root, string word, int id) {
deleteTrieNode(root);
addTrieNode(root, word, id);
}
void Tree::addTrieNode(string word, int id) {
this->addTrieNode(this->root, word, id);
}
void Tree::deleteTrieNode() {
this->deleteTrieNode(this->root);
}
map<int, string> Tree::searchTrie(string word) {
return this->searchTrie(root, word);
}
int Tree::getWordFreq(string word) {
return this->getWordFreq(this->root, word);
}
void Tree::upateTree(string word, int id) {
this->upateTree(this->root, word, id);
}
Client
Client.hpp
//
// Client.hpp
// Trie
//
// Created by staff on 16/9/29.
// Copyright © 2016年 staff. All rights reserved.
//
#ifndef Client_hpp
#define Client_hpp
#include <stdio.h>
#include <iomanip>
#include <fstream>
#include <string>
#include <algorithm>
#include <map>
#include "TreeNode.hpp"
using namespace std;
class Client {
public:
Client();
~Client();
void test();
private:
Tree *tree;
};
#endif /* Client_hpp */
Client.cpp
//
// Client.cpp
// Trie
//
// Created by staff on 16/9/29.
// Copyright © 2016年 staff. All rights reserved.
//
#include "Client.hpp"
Client::Client() {
this->tree = new Tree();
}
Client::~Client() {
}
void Client::test() {
ifstream infile;
infile.open("/Users/George/Desktop/out.txt");
string message;
char buf[1024];
if (infile.is_open()) {
while (infile.good() && !infile.eof()) {
memset(buf, 0, 1024);
infile.getline(buf, 1024);
message = buf;
size_t size = message.length();
size_t space = message.find_first_of(' ');
int id = atoi(message.substr(0, space).c_str());
string word = message.substr(space+1, size-1);
word.erase(word.end()-1);
transform(word.begin(), word.end(), word.begin(), ::tolower);
this->tree->addTrieNode(word, id);
}
char input[20];
printf("please input\n");
scanf("%s", input);
int content_count = this->tree->getWordFreq(input);
printf("content count : %d\n", content_count);
map<int, string> ids = this->tree->searchTrie(input);
int prefix_count = (int)ids.size();
printf("prefix count : %d\n\n", prefix_count);
for (auto id : ids) {
printf("%d:%s\n", id.first, id.second.c_str());
}
}
else {
printf("无法读取文件\n");
}
infile.close();
}
main
//
// main.cpp
// Trie
//
// Created by staff on 16/9/28.
// Copyright © 2016年 staff. All rights reserved.
//
#include <stdio.h>
#include "Client.hpp"
int main(int argc, const char * argv[]) {
// insert code here...
Client * client = new Client();
client->test();
return 0;
}