Name the program for this assignment \"bst_driver.cpp.\" In this assignment you
ID: 3694459 • Letter: N
Question
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:
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
};
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;
add “del_population”;
add “del_population” with a different signature than h 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_population(const double & item); //deletes a county record based on the population size. void del_population(treenode * & loc_ptr, double & item); //see del 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;
};
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_population(string item) deletes a county record based on the population size. Remember the tree is based (indexed) on county name. This function is called from main.
void del_population(treenode * & loc_ptr, string item) is an auxiliary function to help delete a county record based on population size. It is a member function that can only be called by another member of the class.
void del_name(string item) deletes a county record based on county name. This function is called from main. Remember the tree is 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.
//Sample driver. Make correction and changes as necessary
int main( )
{
cout<<"Test1: default constructor ";
bst myTree;
myTree.print_tree();
cout<<"End Test1 ";
cout<<"Test2:insert ";
myTree.insert("new-county", 234658);
myTree.print_tree();
cout<<"End Test2 ";
cout<<"Test3: population_ranges ";
myTree.population_ranges(0,50000);
cout<<"End Test3 ";
cout<<"Test4: del_populaton ";
myTree.del_populaton(173094);
myTree.print_tree();
cout<<"End Test4 ";
cout<<"Test5: del_name ";
myTree.del_name("miami-dade");
cout<<"End Test5 ";
cout<<"Test6: sorted_info ";
myTree.sorted_info();
cout<<"End Test6 ";
return 0;
}
/*
This is a simple program to give the student experience writing code
for binary trees. This is a CLASS implementation of the BST ADT.
The student should study, comment, correct errors, compile,
implement/un-implemented/undeveloped functions, and modify code to make
it more efficient when ever necessary. The student should be able to
discuss the advantages and disadvantages of using such an
implementation.
*/
#include <iostream>
#include <string>
using namespace std;
class treenode
{
public:
string info;
treenode *lchild, *rchild;
};
class BST
{
public:
BST(){root=0;}
~BST();
bool empty();
void insert(string item);
void insert_aux(treenode * &, string item);
void del(string item);
void del_aux(treenode * & loc_ptr, string item);
treenode * search_tree_aux(treenode *,string item);
treenode * search_tree(string item);
treenode * inorder_succ(treenode *);
treenode * parent();
void print_tree();
void print_tree_aux(treenode *);
private:
treenode *root;
};
bool BST::empty()
{
return (root==0);
}
void BST::insert(string item)
{
insert_aux(root,item);
}
void BST::insert_aux(treenode * & loc_ptr,string item)
{
if (loc_ptr==0)
{
loc_ptr = new treenode;
loc_ptr->lchild=loc_ptr->rchild=0;
loc_ptr->info=item;
}
else if (loc_ptr->info>item)
insert_aux(loc_ptr->lchild,item);
else if (loc_ptr->info<item)
insert_aux(loc_ptr->rchild,item);
else
cout<<"the item is already in the tree ";
}
treenode * BST::search_tree(string item)
{
return search_tree_aux(root, item);
}
treenode * BST::search_tree_aux(treenode * loc_ptr, string item)
{
if (loc_ptr!=0)
{
if(loc_ptr->info==item)
return loc_ptr;
else if (loc_ptr->info>item)
return search_tree_aux(loc_ptr->lchild,item);
else
return search_tree_aux(loc_ptr->rchild,item);
}
else
return loc_ptr;
}
void BST::del(string item)
{
del_aux(root,item);
}
void BST::del_aux(treenode * & loc_ptr, string item)
{
if (loc_ptr==0)
cout<<"item not in tree ";
else if (loc_ptr->info > item)
del_aux(loc_ptr->lchild, item);
else if (loc_ptr->info < item)
del_aux(loc_ptr->rchild, item);
else
{
treenode * ptr;
if (loc_ptr->lchild == 0)
{
ptr=loc_ptr->rchild;
delete loc_ptr;
loc_ptr=ptr;
}
else if (loc_ptr->rchild == 0)
{
ptr=loc_ptr->lchild;
delete loc_ptr;
loc_ptr=ptr;
}
else
{
ptr=inorder_succ(loc_ptr);
loc_ptr->info = ptr->info;
del_aux(loc_ptr->rchild, ptr->info);
}
}
}
treenode * BST::inorder_succ(treenode * loc_ptr)
{
treenode *ptr=loc_ptr->rchild;
while(ptr->lchild!=0)
{
ptr=ptr->lchild;
}
return ptr;
}
void BST::print_tree()
{
print_tree_aux(root);
}
void BST::print_tree_aux(treenode * loc_ptr)
{
if (loc_ptr!=0)
{
print_tree_aux(loc_ptr->lchild);
cout<<loc_ptr->info<<endl;
print_tree_aux(loc_ptr->rchild);
}
}
BST::~BST()
{
while (root!=0)
{
del(root->info);
}
}
int main()
{
BST B;
//treenode *root1=0, *root2=0;
string s;
char ch;
string key3;
string key4;
string response;
string r1, r2;
cout<<"enter command, c=count, i=insert item,s=search tree,d=delete item,p=print tree, r = range, e=exit: ";
cin>>ch;
cout<<endl;
while (ch!='e')
{
switch (ch)
{
case 'i' :cout<<"enter string: ";
cin>>s;
B.insert(s);
break;
case 's' :cout<<"enter word to search for: ";
cin>>s;
if (!B.search_tree(s))
cout<<s<<"not in tree ";
else
cout<<s<<" was found in the tree ";
break;
case 'd' :cout<<"enter word to delete: ";
cin>>s;
B.del(s);
break;
case 'p' :cout<<"...printing tree... ";
B.print_tree();
break;
default:break;
}
cout<<"enter command, i=insert item,s=search tree,d=delete item,p=print tree, e=exit: ";
cin>>ch;
cout<<endl;
}
cout<<endl<<"no more binary tree..... ";
return 0;
}
Explanation / Answer
#include <iostream>
#include <string>
using namespace std;
class treenode
{
public:
string country_name;
double population_size;
treenode *lchild, *rchild;
};
class bst
{
public:
bst()
{
root=0;
}
~bst();
bool empty();
void insert(string item);
void insert(treenode * &, string item);
void del_name(string item);
void del_name(treenode * & loc_ptr, string ob);
void del_population(double item);
void del_population(treenode *&loc_ptr, double ob);
treenode * search_tree(treenode *,string item);
treenode * search_tree(string item);
treenode * inorder_succ(treenode *);
treenode * parent();
void print_tree();
void print_tree(treenode *);
private:
treenode *root;
};
bool bst::empty()
{
return (root==0);
}
void bst::insert(string item)
{
insert_aux(root,item);
}
void bst::insert_aux(treenode * & loc_ptr,string item)
{
if (loc_ptr==0)
{
loc_ptr = new treenode;
loc_ptr->lchild=loc_ptr->rchild=0;
loc_ptr->info=item;
}
else if (loc_ptr->info>item)
insert_aux(loc_ptr->lchild,item);
else if (loc_ptr->info<item)
insert_aux(loc_ptr->rchild,item);
else
cout<<"the item is already in the tree ";
}
treenode * bst::search_tree(string item)
{
return search_tree(root, item);
}
treenode * bst::search_tree(treenode * loc_ptr, string item)
{
if (loc_ptr!=0)
{
if(loc_ptr->info==item)
return loc_ptr;
else if (loc_ptr->info>item)
return search_tree(loc_ptr->lchild,item);
else
return search_tree(loc_ptr->rchild,item);
}
else
return loc_ptr;
}
void bst::del_name(string item)
{
del_name(root,item);
}
void bst::del_name(treenode * & loc_ptr, string ob)
{
if (loc_ptr==0)
cout<<"item not in tree ";
else if (loc_ptr->info > ob)
del_name(loc_ptr->lchild, ob);
else if (loc_ptr->info < ob)
del_name(loc_ptr->rchild, ob);
else
{
treenode * ptr;
if (loc_ptr->lchild == 0)
{
ptr=loc_ptr->rchild;
delete loc_ptr;
loc_ptr=ptr;
}
else if (loc_ptr->rchild == 0)
{
ptr=loc_ptr->lchild;
delete loc_ptr;
loc_ptr=ptr;
}
else
{
ptr=inorder_succ(loc_ptr);
loc_ptr->info = ptr->info;
del_name(loc_ptr->rchild, ptr->info);
}
}
}
treenode * bst::inorder_succ(treenode * loc_ptr)
{
treenode *ptr=loc_ptr->rchild;
while(ptr->lchild!=0)
{
ptr=ptr->lchild;
}
return ptr;
}
void bst::print_tree()
{
print_tree(root);
}
void bst::print_tree(treenode * loc_ptr)
{
if (loc_ptr!=0)
{
print_tree(loc_ptr->lchild);
cout<<loc_ptr->info<<endl;
print_tree(loc_ptr->rchild);
}
}
bst::~bst()
{
while (root!=0)
{
del_name(root->info);
}
}
int main()
{
bst B;
//treenode *root1=0, *root2=0;
string s;
char ch;
string key3;
string key4;
string response;
string r1, r2;
cout<<"enter command, c=count, i=insert item,s=search tree,d=delete item,p=print tree, r = range, e=exit: ";
cin>>ch;
cout<<endl;
while (ch!='e')
{
switch (ch)
{
case 'i' :cout<<"enter string: ";
cin>>s;
B.insert(s);
break;
case 's' :cout<<"enter word to search for: ";
cin>>s;
if (!B.search_tree(s))
cout<<s<<"not in tree ";
else
cout<<s<<" was found in the tree ";
break;
case 'd' :cout<<"enter word to delete: ";
cin>>s;
B.del_name(s);
break;
case 'p' :cout<<"...printing tree... ";
B.print_tree();
break;
default:break;
}
cout<<"enter command, i=insert item,s=search tree,d=delete item,p=print tree, e=exit: ";
cin>>ch;
cout<<endl;
}
cout<<endl<<"no more binary tree..... ";
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.