C++ Program for Creation,Insertion,Deletion and Traversing of Dictionary using Binary Search Tree
#include"iostream"
#include<string.h>
using
namespace std;
class
node
{
public:
char data[20];
char meaning[20];
class node *left;
class node * right;
};
class
dict
{
public:
node *root;
void create();
void disp_asc(node *);
void insert(node *
root,node *temp);
int search(node *,char
[]);
int update(node *,char
[]);
node* del(node *,char
[]);
node * min(node *);
};
void
dict ::
create()
{
class node *temp;
int ch;
do
{
temp = new node;
cout<<"\nEnter
Keyword:";
cin>>temp->data;
cout<<"\nEnter
Meaning:";
cin>>temp->meaning;
temp->left = NULL;
temp->right = NULL;
if(root == NULL)
{
root = temp;
}
else
{
insert(root,
temp);
}
cout<<"\nDo u
want to add more (y=1/n=0):";
cin>>ch;
}
while(ch == 1);
}
void
dict
:: insert(node * root,node *temp)
{
if(strcmp
(temp->data, root->data) < 0 )
{
if(root->left
== NULL)
root->left
= temp;
else
insert(root->left,temp);
}
else
{
if(root->right
== NULL)
root->right
= temp;
else
insert(root->right,temp);
}
}
void
dict::
disp_asc(node * root)
{
if( root != NULL)
{
disp_asc(root->left);
cout<<"\n Key
Word :"<<root->data;
cout<<"\t
Meaning :"<<root->meaning;
disp_asc(root->right);
}
}
int
dict ::
search(node * root,char k[20])
{
int c=0;
while(root != NULL)
{
c++;
if(strcmp
(k,root->data) == 0)
{
cout<<"\nNo
of Comparisons:"<<c;
return
1;
}
if(strcmp
(k, root->data) < 0)
root =
root->left;
if(strcmp
(k, root->data) > 0)
root =
root->right;
}
return -1;
}
int
dict ::
update(node * root,char k[20])
{
while(root != NULL)
{
if(strcmp
(k,root->data) == 0)
{
cout<<"\nEnter
New Meaning ofKeyword"<<root->data;
cin>>root->meaning;
return
1;
}
if(strcmp
(k, root->data) < 0)
root =
root->left;
if(strcmp
(k, root->data) > 0)
root =
root->right;
}
return -1;
}
node* dict :: del(node
* root,char k[20])
{
node *temp;
if(root == NULL)
{
cout<<"\nElement
No Found";
return root;
}
if (strcmp(k,root->data)
< 0)
{
root->left =
del(root->left, k);
return root;
}
if (strcmp(k,root->data)
> 0)
{
root->right =
del(root->right, k);
return root;
}
if
(root->right==NULL&&root->left==NULL)
{
temp = root;
delete temp;
return NULL;
}
if(root->right==NULL)
{
temp = root;
root = root->left;
delete temp;
return root;
}
else if(root->left==NULL)
{
temp = root;
root = root->right;
delete temp;
return root;
}
temp = min(root->right);
strcpy(root->data,temp->data);
root->right = del(root->right,
temp->data);
return root;
}
node * dict :: min(node
*q)
{
while(q->left != NULL)
{
q = q->left;
}
return q;
}
int
main()
{
int ch;
dict d;
d.root = NULL;
do
{
cout<<"\n \t
\t \t \t MENU ";
cout<<"\n \t
\t \t \t ==== ";
cout<<"\n1.Create
Dictionary \n2.Display Dictionary \n3.Search Data \n4.Update Data \n5.Delete
Data \nEnter your choice:";
cin>>ch;
switch(ch)
{
case 1:
d.create();
break;
case 2: if(d.root
== NULL)
{
cout<<"\nNo
any Keyword";
}
else
{
d.disp_asc(d.root);
}
break;
case 3: if(d.root
== NULL)
{
cout<<"\nDictionary
is Empty. First add keywords then try again ";
}
else
{
cout<<"\nEnter
Keyword which u want to search:";
char
k[20];
cin>>k;
if(
d.search(d.root,k) == 1)
cout<<"\nKeyword
Found";
else
cout<<"\nKeyword
Not Found";
}
break;
case 4:
if(d.root
== NULL)
{
cout<<"\nDictionary
is Empty. First add keywords then try again ";
}
else
{
cout<<"\nEnter
Keyword which meaning want to update:";
char
k[20];
cin>>k;
if(d.update(d.root,k)
== 1)
cout<<"\nMeaning
Updated";
else
cout<<"\nMeaning
Not Found";
}
break;
case 5:
if(d.root
== NULL)
{
cout<<"\nDictionary
is Empty. First add keywords then try again ";
}
else
{
cout<<"\nEnter
Keyword which u want to delete:";
char
k[20];
cin>>k;
if(d.root
== NULL)
{
cout<<"\nNo
any Keyword";
}
else
{
d.root
= d.del(d.root,k);
}
}
}
}
while(ch<=5);
return 0;
}
Output:
MENU
====
1.Create Dictionary
2.Display
Dictionary
3.Search Data
4.Update Data
5.Delete Data
Enter your choice:1
Enter Keyword:a
Enter Meaning:aa
Do u want to add
more (y=1/n=0):1
Enter Keyword:b
Enter Meaning:bb
Do u want to add
more (y=1/n=0):1
Enter Keyword:c
Enter Meaning:cc
Do u want to add
more (y=1/n=0):1
Enter Keyword:d
Enter Meaning:dd
Do u want to add
more (y=1/n=0):0
MENU
====
1.Create Dictionary
2.Display
Dictionary
3.Search Data
4.Update Data
5.Delete Data
Enter your choice:2
Key Word :a
Meaning :aa
Key Word :b
Meaning :bb
Key Word :c
Meaning :cc
Key Word :d
Meaning :dd
MENU
====
1.Create Dictionary
2.Display Dictionary
3.Search Data
4.Update Data
5.Delete Data
Enter your choice:3
Enter Keyword which
u want to search:d
No of Comparisons:4
Keyword Found
MENU
====
1.Create Dictionary
2.Display
Dictionary
3.Search Data
4.Update Data
5.Delete Data
Enter your choice:5
Enter Keyword which
u want to delete:a
MENU
====
1.Create Dictionary
2.Display
Dictionary
3.Search Data
4.Update Data
5.Delete Data
Enter your choice:2
Key Word :b
Meaning :bb
Key Word :c
Meaning :cc
Key Word :d
Meaning :dd
MENU
====
1.Create Dictionary
2.Display
Dictionary
3.Search Data
4.Update Data
5.Delete Data
Enter your choice:
No comments:
Post a Comment