I am trying to implement trie data structure in C++ using class. In TrieNode class I have a TrieNode *children[26]; array and an isEndOfWord boolean value to determine if it is the end word. In that same class I have other functions appropriate to function like getters and setters and additionally insert and search.
Whenever I try to add a new word it is also setting the bool value as true at the end of each word by setting true to isEndOfWord. But in searching function it is not determining the end of the word. Please guide me as I am new to this data structure, and please comment on the way i write the code and what is the appropriate way to write it(in a Professional way, if interested). Thanks!
#include<cstdio>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
class TrieNode{
private:
TrieNode *children[26];
bool isEndOfWord;
public:
TrieNode(){
for(int i = 0; i < 26; i++){
children[i] = NULL;
}
isEndOfWord = false;
}
bool checkNull(char temp){
cout<<"\nIncheckNULL "<<temp<<" "<<(temp - 'a')<<" \n";
if(children[temp - 'a'] == NULL){
return true;
}
else{
return false;
}
}
void setNode(char temp){
cout<<"Setting node \n";
children[temp - 'a'] = new TrieNode();
}
TrieNode *getNode(char temp){
return children[temp - 'a'];
}
void setEndWord(){
this->isEndOfWord = true;
}
bool getEndWord(){
return this->isEndOfWord;
}
void insert(TrieNode*, string);
bool search(TrieNode*, string);
};
void TrieNode::insert(TrieNode *root, string key){
TrieNode *crawl = root;
//cout<<"key is "<<key<<endl;
int length = sizeof(key)/sizeof(key[0]);
//cout<<"find length\n";
for(int i = 0; key[i] != '\0'; i++){
cout<<"TEST null check key is "<<key[i]<<endl;
if(crawl->checkNull(key[i])){
cout<<"null check key is "<<key[i]<<endl;
crawl->setNode(key[i]);
crawl = crawl->getNode(key[i]);
if(key[i + 1] == '\0'){
cout<<"In setting end word\n";
if(crawl->getEndWord()){
cout<<"Word already exists";
}
else{
crawl->setEndWord();
cout<<"End word setted "<<crawl->getEndWord()<<endl;
}
}
}
else{
if(key[i + 1] == '\0'){
cout<<"In setting end word\n";
if(crawl->getEndWord()){
cout<<"Word already exists";
}
else{
crawl->setEndWord();
cout<<"End word setted\n";
}
}
else{
crawl = crawl->getNode(key[i]);
}
}
}
}
bool TrieNode::search(TrieNode *root, string key){
TrieNode *crawl = root;
cout<<"key is "<<key<<endl;
cout<<"\n In search\n";
int length = sizeof(key)/sizeof(key[0]);
for(int i = 0; key[i] != '\0'; i++){
if(crawl->checkNull(key[i])){
cout<<"INside search checknull"<<endl;
cout<<"Word does not exists"<<"sorry"<<endl;
break;
}
else{
cout<<"IN each character getting getEndWord "<<crawl->getEndWord()<<endl;
if(key[i + 1] == '\0'){
if(crawl->getEndWord()){
cout<<"Word Exists";
}
else{
cout<<"Word does not exists"<<"sorry"<<endl;
break;
}
}
else{
crawl = crawl->getNode(key[i]);
}
}
}
}
int main(){
TrieNode *root = new TrieNode();
cout<<"starting"<<endl;
root->insert(root, "hello");
cout<<"first added"<<endl;
root->insert(root, "anna");
root->insert(root, "anni");
cout<<"words added"<<endl;
root->search(root, "hello");
root->search(root, "anny");
}
Your insert and search functions can be simplified a bit.
Consider this. (Read the comments in the below code, they illustrate what the code does)
void TrieNode::insert(TrieNode *root, string key){
TrieNode *crawl = root;
if (!crawl) {
crawl = new TrieNode();
}
cout << "Adding " << key << " to the trie" << endl;
for (int index = 0, auto str_iterator = str.begin(); str_iterator < str.end(); ++str_iterator, ++index) {
char key_char = *str_iterator;
if(crawl -> checkNull(key_char)){
// If a node representing the char does not exist then make it
crawl -> setNode(key_char);
}
crawl = crawl -> getNode(key_char);
if (index == key.length() - 1) {
// We are at the last character, time to mark an end of word
crawl -> setEndWord();
}
}
}
bool TrieNode::search(TrieNode *root, string key){
TrieNode *crawl = root;
if (!crawl) {
cout << "Trie is empty!" << endl;
return false;
}
cout << "Searching for " << key << " in the trie" << endl;
for (int index = 0, auto str_iterator = str.begin(); str_iterator < str.end(); ++str_iterator, ++index) {
char key_char = *str_iterator;
if(crawl -> checkNull(key_char)){
cout << "Key is not in the trie" << endl;
return false;
}
crawl = crawl -> getNode(key_char);
if (index == key.length() - 1) {
if (!(crawl -> getEndWord())) {
cout << "Word is physically present in trie, but not present as a distinct word" << endl;
return false;
} else {
return true;
}
}
}
cout << "Code should not reach here" << endl; // IMO throw an exception I guess
return false;
}
Take advantage of the power of C++ std::string
Also your whole temp - 'a' logic is a bit iffy to me. I wouldn't much around with ASCII values unless I needed to
Why are you including a whole bunch of C headers? Just iostream should suffice to do what cstdio does.
if(!ptr) is a much more natural way to check for NULL.
In production don't use using namespace std; Instead just preface stuff like cout and endl with std::. The reason for this is to avoid polluting the standard namespace.
Read a good CPP OOP book :). It will help you a lot.
Also I lol'd at anna and anni. Your anna and anni must be proud to be in your trie :D