Created
January 18, 2014 08:39
-
-
Save reterVision/8487831 to your computer and use it in GitHub Desktop.
A simple Trie implementation in CPP.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <string> | |
#include <map> | |
#include <vector> | |
using namespace std; | |
struct Node { | |
char ch; | |
map<char, Node*> children; | |
}; | |
class Trie { | |
public: | |
Trie() { head.ch = -1; }; | |
~Trie(); | |
void build_trie(string words[], int length); | |
void insert(string word); | |
void search(string word, bool &result); | |
void print_tree(map<char, Node*> tree); | |
void print(); | |
protected: | |
Node head; | |
// Keep all newly created node in an array, for the ease of | |
// memory release. | |
vector<Node*> children; | |
}; | |
Trie::~Trie() { | |
for (int i=0; i<children.size(); ++i) { | |
delete children[i]; | |
} | |
} | |
void Trie::build_trie(string words[], int length) { | |
for (int i=0; i<length; ++i) { | |
insert(words[i]); | |
} | |
} | |
void Trie::insert(string word) { | |
map<char, Node*> *current_tree = &head.children; | |
map<char, Node*>::iterator it; | |
for (int i=0; i<word.length(); ++i) { | |
char ch = word[i]; | |
if ((it = current_tree->find(ch)) != current_tree->end()) { | |
current_tree = &it->second->children; | |
continue; | |
} | |
if (it == current_tree->end()) { | |
// Display inserting position in the tree, for debug use | |
// | |
// cout << "Inserting " << ch << endl; | |
// cout << "on layer " << endl; | |
// map<char, Node*>::iterator temp = current_tree->begin(); | |
// for (; temp != current_tree->end(); ++temp) | |
// cout << temp->first << endl; | |
Node* new_node = new Node(); | |
new_node->ch = ch; | |
(*current_tree)[ch] = new_node; | |
// For continuous inserting a word. | |
current_tree = &new_node->children; | |
// For the ease of memory clean up. | |
children.push_back(new_node); | |
} | |
} | |
} | |
void Trie::search(string word, bool &result) { | |
map<char, Node*> current_tree = head.children; | |
map<char, Node*>::iterator it; | |
for (int i=0; i<word.length(); ++i) { | |
if ((it = current_tree.find(word[i])) == current_tree.end()) { | |
result = false; | |
return; | |
} | |
current_tree = it->second->children; | |
} | |
result = true; | |
return ; | |
} | |
void Trie::print_tree(map<char, Node*> tree) { | |
if (tree.empty()) { | |
return; | |
} | |
for (map<char, Node*>::iterator it=tree.begin(); it!=tree.end(); ++it) { | |
cout << it->first << endl; | |
print_tree(it->second->children); | |
} | |
} | |
void Trie::print() { | |
map<char, Node*> current_tree = head.children; | |
print_tree(current_tree); | |
} | |
int main(int argc, char** argv) | |
{ | |
string words[] = {"foo", "bar", "baz", "barz"}; | |
Trie trie; | |
trie.build_trie(words, 4); | |
cout << "All nodes..." << endl; | |
trie.print(); | |
cout << "Searching..." << endl; | |
bool in_trie = false; | |
trie.search("foo", in_trie); | |
cout << "foo " << in_trie << endl; | |
trie.search("fooz", in_trie); | |
cout << "fooz " << in_trie << endl; | |
trie.search("bar", in_trie); | |
cout << "bar " << in_trie << endl; | |
trie.search("baz", in_trie); | |
cout << "baz " << in_trie << endl; | |
trie.search("barz", in_trie); | |
cout << "barz " << in_trie << endl;; | |
trie.search("bbb", in_trie); | |
cout << "bbb " << in_trie << endl;; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment