Data Structure and Algorithm Analysis ---COP3530 Program –Module 11 Total Points
ID: 3824364 • Letter: D
Question
Data Structure and Algorithm Analysis---COP3530
Program –Module 11
Total Points 100
After completing this assignment you will be able to implement a binary search tree (BST).
Name the program for this assignment "bst_driver.cpp." In this assignment you will make several modifications to the BST class in the file “bst.cpp” that I provided. Consider the following:
1. Change the declaration of treenode to
class treenode //node in a BST
{
public:
string county_name;
double population_size;
treenode *lchild, *rchild; //left and right children pointers
};
2. Make the following changes to the BST class:
change the name from “BST” to “bst”;
change default constructor from “BST” to “bst”;
leave “empty” as is;
leave “insert” as is;
change name of “insert_aux” to “insert”;
change name “del” to “del_name”;
change name of “del_aux” to “del_name” with a different signature than f above;
leave “search_tree” as is;
change name of “search_tree_aux” to “search_tree”;
leave “inorder_succ” as is;
leave “print_tree” as is;
change name of “print_tree_aux” to “print_tree”.
leave private area (the state) as is;
consider the following class declaration:
class bst
{
public:
bst (); //store the data file (“county_data.txt”) into initial bst
~bst();//de-allocates dynamic memory allocate for tree
bool empty(); // checks to see if the tree is empty
void insert(const string & item, const double & population); //inserts a county record into bst based on
//county_name.
void insert(treenode * &, string item); //see insert description above
void del_name(string item); //deletes a county record based on county name.
void del_name(treenode * & loc_ptr, string item); //see del description above
treenode * search_tree(treenode *,string item);//returns pointer to node with county name
treenode * search_tree(string item); //see search_tree description above
treenode * inorder_succ(treenode *);//return pointer to inorder successor (based on population
//size;
void population_ranges(const double& min_size, const double & max_size); //prints all county names
//o the screen with a population size between min_size and max_size.
void sorted_info( );//prints each county record to a file called “county_info.txt” sorted by county
//name”.
void print_tree(); //prints the node in the bst in numerical order based on the population size
void print_tree(treenode *);//see description above
private:
treenode *root;
};
3. Notes on implementation of population_ranges, sorted_info, del_population, and del_name are as follows:
The void member function “population_ranges” that accepts two values that represents a population size range and prints all the counties with a population size in the range. Consider the following prototype:
void population_ranges(const double& min_size, const double & max_size);
The void member function “sorted_info” that has no formal parameters. This function will print the county information (name and population) to the file “county_info.txt”. Consider the following prototype that goes inside the class declaration:
void sorted_info( );
void del_name(string item) deletes a county record based on county name. This function is called from main. Remember the tree is sorted (based) on county name
void del_name(treenode * & loc_ptr, string item) is an auxiliary function to help delete a county record based on county name. It is a member function that can only be called by another member of the class.
All the data for this program is stored in the file “county_data.txt”. The county name is listed first, followed by the population size. Separate the class declaration and implementation files. Call the header (declaration) for the bst, “bst.h” and the implementation file, “bst.cpp”. Call the driver, “bst_driver.cpp”.
Please submit your files in a zip file called “unit12.zip” before the due date and time. Please start early, and let me know if you have any questions.
Explanation / Answer
Solution :
//header files
# include <iostream.h>
# include <cstdlib.h>
//declaration of node
struct Node
{
int infor;
struct Node *left;
struct Node *right;
}*root;
// Declaration of class
class BinSearchTree
{
public:
void find(int, Node **, Node **);
void insert(int);
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);
BinSearchTree()
{
root = NULL;
}
};
// main function declaration
int main()
{
int ch, number;
BinSearchTree binsearchtree;
Node *temp;
while (1)
{
cout<<"-----------------"<<endl;
cout<<"Operations on BinarySearchTree"<<endl;
cout<<"-----------------"<<endl;
cout<<"1.Insert an Element "<<endl;
cout<<"2.Delete an Element "<<endl;
cout<<"3.Inorder Traversal of BST"<<endl;
cout<<"4.Preorder Traversal of BST "<<endl;
cout<<"5.Postorder Traversal of BST "<<endl;
cout<<"6.Display the BST"<<endl;
cout<<"7.Quit"<<endl;
cout<<"Enter the choice : ";
cin>>ch;
switch(ch)
{
case 1:
temp = new Node;
cout<<"Enter number to be inserted : ";
cin>>temp->infor;
binsearchtree.insert(root, temp);
case 2:
if (root == NULL)
{
cout<<"Tree is empty, nothing to be delete"<<endl;
continue;
}
cout<<"Enter number to be deleted : ";
cin>>number;
binsearchtree.del(number);
break;
case 3:
cout<<"Inorder Traversal of the BST:"<<endl;
binsearchtree.inorder(root);
cout<<endl;
break;
case 4:
cout<<"Preorder Traversal of the BST:"<<endl;
binsearchtree.preorder(root);
cout<<endl;
break;
case 5:
cout<<"Postorder Traversal of the BST:"<<endl;
binsearchtree.postorder(root);
cout<<endl;
break;
case 6:
cout<<"Display the BST:"<<endl;
binsearchtree.display(root,1);
cout<<endl;
break;
case 7:
exit(1);
default:
cout<<" your choice is wrong"<<endl;
}
}
}
// finding of an element in BST
void BinSerachTree::find(int item, Node **par, Node **loc)
{
Node *ptr, *ptrsave;
if (root == NULL)
{
*loc = NULL;
*par = NULL;
return;
}
if (item == root->infor)
{
*loc = root;
*par = NULL;
return;
}
if (item < root->infor)
ptr = root->left;
else
ptr = root->right;
ptrsave = root;
while (ptr != NULL)
{
if (item == ptr->infor)
{
*loc = ptr;
*par = ptrsave;
return;
}
ptrsave = ptr;
if (item < ptr->infor)
ptr = ptr->left;
else
ptr = ptr->right;
}
*loc = NULL;
*par = ptrsave;
}
//insert an element
void BinSearchTree::insert(Node *tree, Node *newNode)
{
if (root == NULL)
{
root = new Node;
root->infor = newNode->infor;
root->left = NULL;
root->right = NULL;
cout<<"Root Node is Added"<<endl;
return;
}
if (tree->infor == newNode->infor)
{
cout<<"The Element is already in the tree"<<endl;
return;
}
if (tree->infor > newNode->infor)
{
if (tree->left != NULL)
{
insert(tree->left, newNode);
}
else
{
tree->left = newNode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
cout<<"Node Added To the 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 the Right"<<endl;
return;
}
}
}
// delete an element
void BinSearchTree::del(int item)
{
Node *parent, *location;
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
find(item, &parent, &location);
if (location == NULL)
{
cout<<"Item is not present in the 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);
}
// case A
void BinSearchTree::case_a(Node *par, Node *loc )
{
if (par == NULL)
{
root = NULL;
}
else
{
if (loc == par->left)
par->left = NULL;
else
par->right = NULL;
}
}
// case B
void BinSearchTree::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;
}
}
// Case C
void BinSearchTree::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;
}
//Pre Order Traversal
void BinSearchTree::preorder(Node *ptr)
{
if (root == NULL)
{
cout<<"Tree empty"<<endl;
return;
}
if (ptr != NULL)
{
cout<<ptr->info<<" "; // root,left,right
preorder(ptr->left);
preorder(ptr->right);
}
}
//In Order Traversal
void BinSearchTree::inorder(Node *ptr)
{
if (root == NULL)
{
cout<<"Tree empty"<<endl;
return; // left,root,right
}
if (ptr != NULL)
{
inorder(ptr->left);
cout<<ptr->info<<" ";
inorder(ptr->right);
}
}
// Postorder Traversal of BST
void BinSearchTree::postorder(Node *ptr)
{
if (root == NULL)
{
cout<<"empty tree"<<endl;
return;
}
if (ptr != NULL) //ptr != null
{
postorder(ptr->left); // left,right,root
postorder(ptr->right);
cout<<ptr->info<<" ";
}
}
//Display the Tree Structure
void BinSearchTree::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->infor;
display(ptr->left, level+1);
}
}
//** Thank You ** //
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.