Sunday, October 27, 2013

Dictionary Problem: Binary Search Tree implementation in C++

#include<iostream>
#include<string.h>
using namespace std;
class node
{
public:
char keyword[20];
char description[30];
node *left,*right;
friend class bst;
};
class bst
{
node *root,*New,*temp;
public:
bst()
{
root = NULL;
}
void create();
void display();
void inorder(node *);
void search(node *,char[]);
void insert(node *,node *);
void del(node *,char[]);
void dels();
void find();
void mirror(node *);
};
void bst::create()
{
New = new node;
New -> left = NULL;
New -> right = NULL;
cout << "Enter Keyword:";
cin >> New -> keyword;
cout << "Enter Meaning:";
cin >> New -> description;
if (root == NULL)
root = New;
else
insert(root,New);
}
void bst::display()
{
if(root==NULL)
{
cout << "\nDictionary not yet created!";
}
else
{
int d;
cout << "Choose :\n1.Ascending\t2.Descending"<<endl;
cin >> d;
cout << "The dictionary is : \n";
if (d == 1)
inorder(root);
else
mirror(root);
}
}
void bst::inorder(node *temp)
{
if(temp != NULL)
{
inorder(temp -> left);
cout << temp -> keyword << ":";
cout << temp -> description << "\n";
inorder(temp -> right);
}
}
void bst::mirror(node *temp)
{
if(temp != NULL)
{
mirror(temp -> right);
cout << temp -> keyword << ":";
cout << temp -> description << "\n";
mirror(temp -> left);
}
}
void bst::insert(node *root, node *New)
{
int d;
d = strcmp(New -> keyword,root -> keyword);
if(d < 0)
{
if (root -> left == NULL)
root -> left = New;
else
insert(root -> left,New);
}
if(d > 0)
{
if(root -> right == NULL)
root -> right = New;
else
insert(root -> right,New);
}
}
void bst::find()
{
char find[20];
cout << "\n Enter the word you want to find:";
cin >> find;
temp = root;
search(temp,find);
}
void bst::search(node *temp,char find[20])
{
int f = 0;
if(temp == NULL)
{
f = 1;
cout << "\nDictionary is not yet created!";
}
else
while(temp != NULL)
{
int d = strcmp(temp -> keyword,find);
if (d == 0)
{
char ch;
f = 1;
cout << "Keyword found :\n";
cout << temp -> keyword << ":" << temp -> description;
cout << "\nDo you want to update the meaning? (y/n)";
cin >> ch;
if(ch == 'y')
{
cout << "Enter the new meaning:";
cin >> temp -> description;
}
break;
}
if(d > 0)
{
temp = temp -> left;
}
if(d < 0)
{
temp = temp -> right;
}
}
if(f == 0)
{
cout << "Not found!";
}
}
void bst::dels()
{
char del[20];
cout << "Enter keyword to delete:";
cin >> del;
temp = root;
New = NULL;
int f = 0;
if(temp == NULL)
{
f = 1;
cout << "\nDictionary is not yet created!";
}
else
while(temp != NULL)
{
int d = strcmp(temp -> keyword,del);
if (d == 0)
{
f = 1;
break;
}
if(d > 0)
{
New = temp;
temp = temp -> left;
}
if(d < 0)
{
New = temp;
temp = temp -> right;
}
}
if(f == 0)
{
cout << "Not found!";
}
else
{
if(temp -> left != NULL && temp -> right != NULL)
{
New = temp;
node *cs;
cs = temp -> right;
while(cs -> left != NULL)
{
New = cs;
cs = cs -> left;
}
strcpy(temp -> description,cs -> description);
strcpy(temp -> keyword,cs -> keyword);
temp = cs;
}
if(temp -> left == NULL && temp -> right == NULL)
{
if(New -> right == temp)
New -> right = NULL;
else
New -> left = NULL;
temp -> left = NULL;
temp -> right = NULL;
delete(temp);
}
if(temp -> left == NULL && temp -> right != NULL)
{
if(New -> left == temp)
New -> left = temp -> right;
else
New -> right = temp -> right;
delete(temp);
}
if(temp -> left != NULL && temp -> right == NULL)
{
if(New -> left == temp)
New -> left = temp -> left;
else
New -> right = temp -> left;
delete(temp);
}
}
}
int main()
{
int ch;
char f;
bst a;
do
{
cout<<"Select Operation -\n1.Create\n2.Display\n3.Search\n4.Delete\n5.Stop"<<endl;
cin>>ch;
switch(ch)
{
case 1:
do
{
a.create();
cout << "\nDo you wish to enter more words?(y/n)";
cin >> f;
}
while(f == 'y');
break;
case 2:
a.display();
break;
case 3:
a.find();
break;
case 4:
a.dels();
break;
case 5:
break;
default:
cout << "Incorrect Option";
break;
}
}
while(ch != 5);
return 0;
}

#include<iostream>
#include<string.h>
using namespace std;
class node
{
public:
char keyword[20];
char description[30];
node *left,*right;
friend class bst;
};
class bst
{
node *root,*New,*temp;
public:
bst()
{
root = NULL;
}
void create();
void display();
void inorder(node *);
void search(node *,char[]);
void insert(node *,node *);
void del(node *,char[]);
void dels();
void find();
void mirror(node *);
};
void bst::create()
{
New = new node;
New -> left = NULL;
New -> right = NULL;
cout << "Enter Keyword:";
cin >> New -> keyword;
cout << "Enter Meaning:";
cin >> New -> description;
if (root == NULL)
root = New;
else
insert(root,New);
}
void bst::display()
{
if(root==NULL)
{
cout << "\nDictionary not yet created!";
}
else
{
int d;
cout << "Choose :\n1.Ascending\t2.Descending"<<endl;
cin >> d;
cout << "The dictionary is : \n";
if (d == 1)
inorder(root);
else
mirror(root);
}
}
void bst::inorder(node *temp)
{
if(temp != NULL)
{
inorder(temp -> left);
cout << temp -> keyword << ":";
cout << temp -> description << "\n";
inorder(temp -> right);
}
}
void bst::mirror(node *temp)
{
if(temp != NULL)
{
mirror(temp -> right);
cout << temp -> keyword << ":";
cout << temp -> description << "\n";
mirror(temp -> left);
}
}
void bst::insert(node *root, node *New)
{
int d;
d = strcmp(New -> keyword,root -> keyword);
if(d < 0)
{
if (root -> left == NULL)
root -> left = New;
else
insert(root -> left,New);
}
if(d > 0)
{
if(root -> right == NULL)
root -> right = New;
else
insert(root -> right,New);
}
}
void bst::find()
{
char find[20];
cout << "\n Enter the word you want to find:";
cin >> find;
temp = root;
search(temp,find);
}
void bst::search(node *temp,char find[20])
{
int f = 0;
if(temp == NULL)
{
f = 1;
cout << "\nDictionary is not yet created!";
}
else
while(temp != NULL)
{
int d = strcmp(temp -> keyword,find);
if (d == 0)
{
char ch;
f = 1;
cout << "Keyword found :\n";
cout << temp -> keyword << ":" << temp -> description;
cout << "\nDo you want to update the meaning? (y/n)";
cin >> ch;
if(ch == 'y')
{
cout << "Enter the new meaning:";
cin >> temp -> description;
}
break;
}
if(d > 0)
{
temp = temp -> left;
}
if(d < 0)
{
temp = temp -> right;
}
}
if(f == 0)
{
cout << "Not found!";
}
}
void bst::dels()
{
char del[20];
cout << "Enter keyword to delete:";
cin >> del;
temp = root;
New = NULL;
int f = 0;
if(temp == NULL)
{
f = 1;
cout << "\nDictionary is not yet created!";
}
else
while(temp != NULL)
{
int d = strcmp(temp -> keyword,del);
if (d == 0)
{
f = 1;
break;
}
if(d > 0)
{
New = temp;
temp = temp -> left;
}
if(d < 0)
{
New = temp;
temp = temp -> right;
}
}
if(f == 0)
{
cout << "Not found!";
}
else
{
if(temp -> left != NULL && temp -> right != NULL)
{
New = temp;
node *cs;
cs = temp -> right;
while(cs -> left != NULL)
{
New = cs;
cs = cs -> left;
}
strcpy(temp -> description,cs -> description);
strcpy(temp -> keyword,cs -> keyword);
temp = cs;
}
if(temp -> left == NULL && temp -> right == NULL)
{
if(New -> right == temp)
New -> right = NULL;
else
New -> left = NULL;
temp -> left = NULL;
temp -> right = NULL;
delete(temp);
}
if(temp -> left == NULL && temp -> right != NULL)
{
if(New -> left == temp)
New -> left = temp -> right;
else
New -> right = temp -> right;
delete(temp);
}
if(temp -> left != NULL && temp -> right == NULL)
{
if(New -> left == temp)
New -> left = temp -> left;
else
New -> right = temp -> left;
delete(temp);
}
}
}
int main()
{
int ch;
char f;
bst a;
do
{
cout<<"Select Operation -\n1.Create\n2.Display\n3.Search\n4.Delete\n5.Stop"<<endl;
cin>>ch;
switch(ch)
{
case 1:
do
{
a.create();
cout << "\nDo you wish to enter more words?(y/n)";
cin >> f;
}
while(f == 'y');
break;
case 2:
a.display();
break;
case 3:
a.find();
break;
case 4:
a.dels();
break;
case 5:
break;
default:
cout << "Incorrect Option";
break;
}
}
while(ch != 5);
return 0;
}


at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)

Perform a suitable assignment using Xen Hypervisor or equivalent open source to configure it. Give necessary GUI.

 To install kvm on Fedora:  yum install kvm  yum install virt-manager libvirt libvirt-python python-virtinst  su -c "yum install @v...