Please Show sample Run . Implement a city database using a Binary Search Tree (B
ID: 3572766 • Letter: P
Question
Please Show sample Run .
Implement a city database using a Binary Search Tree (BST) to store the database records. Each database record contains the name of the city (a string of arbitrary length) and the coordinates of the city expressed as integer x- and y-coordinates. The BST should be organized by city name. Your database should allow records to be inserted, deleted by name or coordinate, and searched by name or coordinate. Another operation that should be supported is to print all records within a given distance of a specified point. Write a C++ code to implement the city database.Explanation / Answer
# include <iostream>
# include <cstdlib>
using namespace std;
struct node
{
char city[100];
int x;
int y;
struct node *left;
struct node *right;
}*root;
class BST
{
public:
void find(string, node **, node **);
void insert(node *,node *);
void del(int);
void case_a(node *,node *);
void case_b(node *,node *);
void case_c(node *,node *);
void preorder(node *);
void inorder(node *);
void postorder(node *);
void display(node *, int);
BST()
{
root = NULL;
}
};
int main()
{
int choice, num;
BST bst;
node *temp;
while (1)
{
cout<<"-----------------"<<endl;
cout<<"Operations on BST"<<endl;
cout<<"-----------------"<<endl;
cout<<"1.Insert Element "<<endl;
cout<<"2.Delete Element "<<endl;
cout<<"3.Inorder Traversal"<<endl;
cout<<"4.Preorder Traversal"<<endl;
cout<<"5.Postorder Traversal"<<endl;
cout<<"6.Display"<<endl;
cout<<"7.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
temp = new node;
cout<<"Enter the city to be inserted : ";
cin>>temp->city;
bst.insert(root, temp);
case 2:
if (root == NULL)
{
cout<<"Tree is empty, nothing to delete"<<endl;
continue;
}
cout<<"Enter the number to be deleted : ";
cin>>city;
bst.del(city);
break;
case 3:
cout<<"Inorder Traversal of BST:"<<endl;
bst.inorder(root);
cout<<endl;
break;
case 4:
cout<<"Preorder Traversal of BST:"<<endl;
bst.preorder(root);
cout<<endl;
break;
case 5:
cout<<"Postorder Traversal of BST:"<<endl;
bst.postorder(root);
cout<<endl;
break;
case 6:
cout<<"Display BST:"<<endl;
bst.display(root,1);
cout<<endl;
break;
case 7:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}
}
}
void BST::find(string item, node **par, node **loc)
{
node *ptr, *ptrsave;
if (root == NULL)
{
*loc = NULL;
*par = NULL;
return;
}
if (item == root->city)
{
*loc = root;
*par = NULL;
return;
}
if (item < root->city)
ptr = root->left;
else
ptr = root->right;
ptrsave = root;
while (ptr != NULL)
{
if (item == ptr->city)
{
*loc = ptr;
*par = ptrsave;
return;
}
ptrsave = ptr;
if (item < ptr->city)
ptr = ptr->left;
else
ptr = ptr->right;
}
*loc = NULL;
*par = ptrsave;
}
void BST::insert(node *tree, node *newnode)
{
if (root == NULL)
{
root = new node;
root->city = newnode->city;
root->left = NULL;
root->right = NULL;
cout<<"Root Node is Added"<<endl;
return;
}
if (tree->city == newnode->city)
{
cout<<"Element already in the tree"<<endl;
return;
}
if (tree->city > newnode->city)
{
if (tree->left != NULL)
{
insert(tree->left, newnode);
}
else
{
tree->left = newnode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
cout<<"Node Added To Left"<<endl;
return;
}
}
else
{
if (tree->right != NULL)
{
insert(tree->right, newnode);
}
else
{
tree->right = newnode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
cout<<"Node Added To Right"<<endl;
return;
}
}
}
void BST::del(string item)
{
node *parent, *location;
if (root == NULL)
{
cout<<"Tree empty"<<endl;
return;
}
find(item, &parent, &location);
if (location == NULL)
{
cout<<"Item not present in tree"<<endl;
return;
}
if (location->left == NULL && location->right == NULL)
case_a(parent, location);
if (location->left != NULL && location->right == NULL)
case_b(parent, location);
if (location->left == NULL && location->right != NULL)
case_b(parent, location);
if (location->left != NULL && location->right != NULL)
case_c(parent, location);
free(location);
}
void BST::case_a(node *par, node *loc )
{
if (par == NULL)
{
root = NULL;
}
else
{
if (loc == par->left)
par->left = NULL;
else
par->right = NULL;
}
}
void BST::case_b(node *par, node *loc)
{
node *child;
if (loc->left != NULL)
child = loc->left;
else
child = loc->right;
if (par == NULL)
{
root = child;
}
else
{
if (loc == par->left)
par->left = child;
else
par->right = child;
}
}
void BST::case_c(node *par, node *loc)
{
node *ptr, *ptrsave, *suc, *parsuc;
ptrsave = loc;
ptr = loc->right;
while (ptr->left != NULL)
{
ptrsave = ptr;
ptr = ptr->left;
}
suc = ptr;
parsuc = ptrsave;
if (suc->left == NULL && suc->right == NULL)
case_a(parsuc, suc);
else
case_b(parsuc, suc);
if (par == NULL)
{
root = suc;
}
else
{
if (loc == par->left)
par->left = suc;
else
par->right = suc;
}
suc->left = loc->left;
suc->right = loc->right;
}
void BST::preorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
cout<<ptr->city<<" ";
preorder(ptr->left);
preorder(ptr->right);
}
}
void BST::inorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
inorder(ptr->left);
cout<<ptr->city<<" ";
inorder(ptr->right);
}
}
void BST::postorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
postorder(ptr->left);
postorder(ptr->right);
cout<<ptr->city<<" ";
}
}
void BST::display(node *ptr, int level)
{
int i;
if (ptr != NULL)
{
display(ptr->right, level+1);
cout<<endl;
if (ptr == root)
cout<<"Root->: ";
else
{
for (i = 0;i < level;i++)
cout<<" ";
}
cout<<ptr->city;
display(ptr->left, level+1);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.