2.BST_dictionary

File: /home/saiesh/ADS/Assignment No 2/ads2.cpp
#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;
typedef struct node
{
char word[30];
char meaning[50];
node *left,*right;
}bstnode;
bstnode *root;
class BST
{
public:
BST()
{
root=NULL;
}
bstnode *getnode();
void create();
void inorder(bstnode *T);
void comparison(bstnode *root);
void update(bstnode *root);
bstnode *deletenode(bstnode *root,char word[30]);
};
bstnode *BST::getnode()
{
bstnode *temp;
temp=new bstnode;
cout<<"\nEnter the word:\t\t";
cin>>temp->word;
cout<<"Enter the meaning:\t";
cin>>temp->meaning;
temp->left=temp->right=NULL;
return temp;
}
void BST::create()
{
char ch;
bstnode *temp, *ptr;
do
{
temp=getnode();
if(root==NULL)
root=temp;
else
{
ptr=root;
while(1)
{
if(strcmp(temp->word,ptr->word)<0)
{
if(ptr->left==NULL)
{
ptr->left=temp;
break;
}
else
ptr=ptr->left;
}
else
Page 1 of 7File: /home/saiesh/ADS/Assignment No 2/ads2.cpp
{
if(ptr->right==NULL)
{
ptr->right=temp;
break;
}
else
ptr=ptr->right;
}
}
}
cout<<"Do you want to enter more keywords? ";
cin>>ch;
} while(ch=='y'||ch=='Y');
}
void BST::inorder(bstnode *T)
{
if(T!=NULL)
{
inorder(T->left);
cout<<"\n"<<T->word<<"\t"<<T->meaning;
inorder(T->right);
}
}
void BST::comparison(bstnode*root)
{
bstnode *ptr;
ptr=root;
int i=0;
char word[30];
cout<<"\nEnter the word you need to compare: ";
cin>>word;
while(ptr!=NULL)
{
if(strcmp(word,ptr->word)==0)
{
cout<<"\nWord:\t\t"<<word;
cout<<"\nMeaning:\t"<<ptr->meaning<<"\n";
i++;
break;
}
else
i++;
if(strcmp(word,ptr->word)<0)
ptr=ptr->left;
else
ptr=ptr->right;
}
cout<<"Total number of comparisons: "<<i;
}
void BST::update(bstnode *root)
{
bstnode *ptr;
ptr=root;
char word[30];
cout<<"\nEnter the word you need to update: ";
cin>>word;
while(ptr!=NULL)
{
if(strcmp(word,ptr->word)==0)
{
cout<<"\nWord:\t\t"<<word;
cout<<"\nNew Meaning:\t";
Page 2 of 7File: /home/saiesh/ADS/Assignment No 2/ads2.cpp
cin>>ptr->meaning;
return ;
}
else if(strcmp(word,ptr->word)<0)
ptr=ptr->left;
else
ptr=ptr->right;
}
cout<<"The word you want to update is not found.";
}
bstnode *BST::deletenode(bstnode *root,char word[30])
{
bstnode *T,*P,*tsucc;
T=root;
while(T!=NULL)
{
if(strcmp(T->word,word)==0)
break;
P=T;
if(strcmp(P->word,word)>0)
T=T->left;
else
T=T->right;
}
if(T==NULL)
cout<<"Element not found.";
else if(T->left==NULL&&T->right==NULL)
{
if(T==root)
root==NULL;
else if(strcmp(P->word,T->word)>0)
P->left=NULL;
else
P->right=NULL;
delete T;
}
else if(T->left!=NULL&&T->right==NULL)
{
if(T==root)
root=T->left;
else if(strcmp(P->word,T->word)>0)
P->left=T->left;
else
P->right=T->left;
delete T;
}
else if(T->left==NULL&&T->right!=NULL)
{
if(T==NULL)
root=T->right;
else if(strcmp(P->word,T->word)>0)
P->left=T->right;
else
P->right=T->right;
delete T;
}
else if(T->left!=NULL&&T->right!=NULL)
{
tsucc = T->right;
while(tsucc->left!=NULL)
tsucc = tsucc->left;
strcpy(T->word,tsucc->word);
strcpy(T->meaning,tsucc->meaning);
T->right=deletenode(T->right,tsucc->word);
}
Page 3 of 7File: /home/saiesh/ADS/Assignment No 2/ads2.cpp
Page 4 of 7
else
delete T;
}
int main()
{
BST obj;
char ans,word[30];
int ch,S;
do
{
cout<<"\n\t\t
MENU";
cout<<"\n1.Insert new node";
cout<<"\n2.Display nodes";
cout<<"\n3.Compare node";
cout<<"\n4.Update node";
cout<<"\n5.Delete node";
cout<<"\n6.Exit";
cout<<"\nEnter your choice:\t";
cin>>ch;
switch(ch)
{
case 1: obj.create();
break;
case 2: cout<<"\nWord\tMeaning";
obj.inorder(root);
break;
case 3: obj.comparison(root);
break;
case 4: obj.update(root);
cout<<"\nWord\tMeaning";
obj.inorder(root);
break;
case 5: cout<<"\nEnter the word you want to delete: ";
cin>>word;
obj.deletenode(root,word);
cout<<"\nWord\tMeaning";
obj.inorder(root);
break;
case 6: exit(0);
}
cout<<"\nDo you want to continue? ";
cin>>ans;
} while(ans=='y'||ans=='Y');
return 0;
}
/*
OUTPUT
saiesh@saiesh :~$ g++ ads2.cpp
saiesh@saiesh :~$ ./a.out
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Delete node
6.Exit
Enter your choice:
1
Enter the word:
honey
Enter the meaning:
sweet
Do you want to enter more keywords? y
Enter the word:
domeFile: /home/saiesh/ADS/Assignment No 2/ads2.cpp
Enter the meaning:
igloo
Do you want to enter more keywords? y
Enter the word:
stop
Enter the meaning:
terminate
Do you want to enter more keywords? y
Enter the word:
back
Enter the meaning:
reverse
Do you want to enter more keywords? y
Enter the word:
ear
Enter the meaning:
organ
Do you want to enter more keywords? y
Enter the word:
apple
Enter the meaning:
fruit
Do you want to enter more keywords? y
Enter the word:
father
Enter the meaning:
dad
Do you want to enter more keywords? y
Enter the word:
farm
Enter the meaning:
shed
Do you want to enter more keywords? n
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Delete node
6.Exit
Enter your choice:
2
Word
Meaning
apple
fruit
back
reverse
dome
igloo
ear
organ
farm
shed
father dad
honey
sweet
stop
terminate
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Delete node
6.Exit
Enter your choice:
3
Enter the word you need to compare: apple
Word:
apple
Meaning:
fruit
Total number of comparisons: 4
Do you want to continue? y
MENU
Page 5 of 7File: /home/saiesh/ADS/Assignment No 2/ads2.cpp
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Delete node
6.Exit
Enter your choice:
3
Enter the word you need to compare: window
Total number of comparisons: 2
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Delete node
6.Exit
Enter your choice:
4
Enter the word you need to update: back
Word:
New Meaning:
back
rewind
Word
Meaning
apple
fruit
back
rewind
dome
igloo
ear
organ
farm
shed
father dad
honey
sweet
stop
terminate
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Delete node
6.Exit
Enter your choice:
5
Enter the word you want to delete: apple
Word
Meaning
back
rewind
dome
igloo
ear
organ
farm
shed
father dad
honey
sweet
stop
terminate
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Delete node
6.Exit
Enter your choice:
5
Page 6 of 7File: /home/saiesh/ADS/Assignment No 2/ads2.cpp
Enter the word you want to delete: farm
Word
Meaning
back
rewind
dome
igloo
ear
organ
father dad
honey
sweet
stop
terminate
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Delete node
6.Exit
Enter your choice:
5
Enter the word you want to delete: father
Word
Meaning
back
rewind
dome
igloo
ear
organ
honey
sweet
stop
terminate
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Delete node
6.Exit
Enter your choice:
5
Enter the word you want to delete: honey
Word
back
dome
ear
stop
Meaning
rewind
igloo
organ
terminate
Do you want to continue? y
MENU
1.Insert new node
2.Display nodes
3.Compare node
4.Update node
5.Delete node
6.Exit
Enter your choice:
saiesh@saiesh :~$ */
6
Page 7 of 7