This is a working program for Ternary Search Trees in this we can store and match the string....etc. It has taken the advantages of time efficiency of Tries and memory efficiency of BST.
Ex: For the words BOAT BOOM BOSS BOK
#include <stdlib.h>
typedef struct TSTNode
{
char data;
int eos;
struct TSTNode *left;
struct TSTNode *curr;
struct TSTNode *right;
}TST;
TST *Insert(TST *Root,char word[])
{
if(!*word)return Root;
if(!Root)
{
TST *newnode;
newnode=(TST*)malloc(sizeof(TST));
newnode->data=*word;
newnode->eos=0;
newnode->left=newnode->right=newnode->curr=NULL;
if(!*(word+1))
newnode->eos=1;
else
newnode->curr=Insert(newnode->curr,word+1);
return newnode;
}
else if(Root->data>*word)
Root->left=Insert(Root->left,word);
else if(Root->data<*word)
Root->right=Insert(Root->right,word);
else
{
if(!*(word+1))
Root->eos=1;
else
Root->curr=Insert(Root->curr,word+1);
}
return Root;
}
void Search(TST *Root,char word[])
{
if(!Root)
{
printf("NOT FOUND");
return;
}
if(Root->data>*word)
Search(Root->left,word);
else if(Root->data<*word)
Search(Root->right,word);
else
{
if(!*(word+1))
{ if(Root->eos==1)
printf("FOUND");
else
printf("NOT FOUND");
return;
}
Search(Root->curr,word+1);
}
}
void Traverse(TST *Root,char *buffer,int depth)
{
if(!Root) return ;
Traverse(Root->left,buffer,depth);
buffer[depth]=Root->data;
if(Root->eos)
{ buffer[depth+1]='\0';
printf("%s\n",buffer);
}
Traverse(Root->curr,buffer,depth+1);
Traverse(Root->right,buffer,depth);
}
int main(void)
{int i=0;
char word[20];
TST *Root=NULL;
while(i<7)
{
scanf("%s%*c",word);
Root=Insert(Root,word);
i++;
}
printf("Traversal of tree is \n");
Traverse(Root,word,0);
printf("Enter the string to search.....\n");
scanf("%s%*c",word);
printf("%s\n",word);
Search(Root,word);
return 0;
}
Happy Coding
Ex: For the words BOAT BOOM BOSS BOK
B | O | A | \ T S / | O S / | K M This is how it will be represented in the memory.#include <stdio.h>
#include <stdlib.h>
typedef struct TSTNode
{
char data;
int eos;
struct TSTNode *left;
struct TSTNode *curr;
struct TSTNode *right;
}TST;
TST *Insert(TST *Root,char word[])
{
if(!*word)return Root;
if(!Root)
{
TST *newnode;
newnode=(TST*)malloc(sizeof(TST));
newnode->data=*word;
newnode->eos=0;
newnode->left=newnode->right=newnode->curr=NULL;
if(!*(word+1))
newnode->eos=1;
else
newnode->curr=Insert(newnode->curr,word+1);
return newnode;
}
else if(Root->data>*word)
Root->left=Insert(Root->left,word);
else if(Root->data<*word)
Root->right=Insert(Root->right,word);
else
{
if(!*(word+1))
Root->eos=1;
else
Root->curr=Insert(Root->curr,word+1);
}
return Root;
}
void Search(TST *Root,char word[])
{
if(!Root)
{
printf("NOT FOUND");
return;
}
if(Root->data>*word)
Search(Root->left,word);
else if(Root->data<*word)
Search(Root->right,word);
else
{
if(!*(word+1))
{ if(Root->eos==1)
printf("FOUND");
else
printf("NOT FOUND");
return;
}
Search(Root->curr,word+1);
}
}
void Traverse(TST *Root,char *buffer,int depth)
{
if(!Root) return ;
Traverse(Root->left,buffer,depth);
buffer[depth]=Root->data;
if(Root->eos)
{ buffer[depth+1]='\0';
printf("%s\n",buffer);
}
Traverse(Root->curr,buffer,depth+1);
Traverse(Root->right,buffer,depth);
}
int main(void)
{int i=0;
char word[20];
TST *Root=NULL;
while(i<7)
{
scanf("%s%*c",word);
Root=Insert(Root,word);
i++;
}
printf("Traversal of tree is \n");
Traverse(Root,word,0);
printf("Enter the string to search.....\n");
scanf("%s%*c",word);
printf("%s\n",word);
Search(Root,word);
return 0;
}
Happy Coding
No comments:
Post a Comment