Coding a Trie

Definition :

Trie is also called Digital Tree (sometimes Radix Tree or Prefix Tree).It is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings.

Solution:

/*
Trie Data Structure

Submitetd By
Arjun Mishra
*/

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
using namespace std;
#define MAX_SIZE 26

//data structure for Trie<only for small letters>
struct Trie
{
int count;
int leaf;
struct Trie* next[MAX_SIZE];
Trie()//constructor
{
count=0;//initially not visited
leaf=0;//initially 0, means not a leaf
for(int i=0;i<MAX_SIZE;i++)
next[i]=NULL;//initially NULL
}
}*root,*ptr;

//function to insert into a trie
void insert(char str[6],int index,int len,struct Trie *R)
{
if(index==len)
{
return;
}
if(R->next[str[index]-'a']==NULL)
{
ptr=new Trie();
R->next[str[index]-'a']=ptr;
}
R->next[str[index]-'a']->count+=1;
if(index==(len-1))
R->next[str[index]-'a']->leaf=1;
insert(str,index+1,len,R->next[str[index]-'a']);
}

//function to traverse a trie
void getWords(struct Trie *R,char o[51],int index)
{

if(R==NULL)
return;
for(int i=0;i<MAX_SIZE;i++)
{
if(R->next[i]!=NULL)
{
//cout<<index<<endl;
o[index]=char(i+97);
if(R->next[i]->leaf==1)
{
for(int j=0;j<=index;j++)
cout<<o[j];
cout<<endl;
}
getWords(R->next[i],o,index+1);
}
}
}

//function to perform sleep operation
void sleep(int time_in_sec)
{
int start=clock();
while(clock()<=(start+time_in_sec*1000))
{
//empty loop
}
}

//main function, driver utility
int main()
{
ptr=new Trie();
root=ptr;
while(1)
{
int ch;
char str[51]={};
char o[51]={};
cout<<"Menu :\n\n";
cout<<"Enter 0 to exit\n";
cout<<"Enter 1 to insert into the dictionary\n";
cout<<"Enter 2 to traverse dictionary\n";
cout<<"\nEnter your choice :";
cin>>ch;
switch(ch)
{
case 0:
system("cls");
cout<<"Application By :\n\nArjun Mishra\nFinal Year Student\nMNNIT Allahabad";
return 0;
case 1:
system("cls");
cout<<"Insert word :";
scanf(" %s",str);
insert(str,0,strlen(str),root);
system("cls");
break;
case 2:
system("cls");
cout<<"All inserted words are\n\n";
getWords(root,o,0);
cout<<"\n\nPlease Wait...";
sleep(5);
system("cls");
break;
default:
system("cls");
cout<<"Wrong Choice\n";
sleep(2);
system("cls");
}
}
return 0;

}