Hello everyone,
I was trying to implement Trie in c++ for the first time and got some
issues in coding its implementation.
The code has 2 commented lines namely cmnt1 and cmnt 2.
I dont understand how does it make a difference if i use cmnt1 instead of
cmnt2 .
Both lines are intended to check if a node in the Trie has childs never
initialized before.
----------------------------- Code Below
-----------------------------------------------
#include <fstream>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
using namespace std;
struct TrieNode
{
bool leaf;
TrieNode* symbol;
};
void child(TrieNode* T)
{
////cmnt1////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////if( T->symbol != NULL)return;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
T->symbol=(TrieNode*)malloc(26*sizeof(TrieNode));
for(int i=0;i<26;i++)
{ T->symbol[i].leaf=false;
T->symbol[i].symbol=NULL;
}
}
TrieNode* makeTrie( )
{
TrieNode* T=(TrieNode*)malloc(sizeof(TrieNode));
T->leaf=false;
child(T);
return T;
}
void insert(string A,TrieNode* root)
{TrieNode* temp=root;
int i;
for(i=0;i<A.length()-1;i++)
{ temp=&(temp->symbol[A[i]-'A']);
//cmnt2//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
if( temp->symbol== NULL)
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
child(temp);
}
temp=&(temp->symbol[A[i]-'A']);
temp->leaf=true;
}
vector<char> display;
void print(TrieNode* T)
{
if(T->leaf==true){ for(int i=0;i<display.size();i++)cout<<display[i]<<"
";cout<<endl; }
if(T==NULL)return;
if(T->symbol!=NULL){
for(int i=0;i<26;i++)
{
display.push_back('A'+i);
print(&T->symbol[i]);
display.pop_back(); }
}
}
int main()
{
TrieNode* root=makeTrie();
insert("ADI",root);
insert("CAT",root);
insert("ADII",root);
print(root);
// system("pause");
}
-----------------end of code---------------------
if i remove code of cmnt 1(like in the pasted code) and directly use the
code of cmnt 2 then trie code runs smooth .But if do the opposite case
,which is logically the same ,the code fails to run. kindly help!
--
