Name the program for this assignment \"bst_driver.cpp.\" In this assignment you
ID: 3919862 • 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:
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:
a) change the name from “BST” to “bst”;
b) change default constructor from “BST” to “bst”;
c) leave “empty” as is;
d) leave “insert” as is;
e) change name of “insert_aux” to “insert”;
f) change name “del” to “del_name”;
g) change name of “del_aux” to “del_name” with a different signature than f above;
h) leave “search_tree” as is;
i) change name of “search_tree_aux” to “search_tree”;
j) leave “inorder_succ” as is;
k) leave “print_tree” as is;
l) change name of “print_tree_aux” to “print_tree”.
m) leave private area (the state) as is;
n) 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 county name.
void county_ranges(const string min_name, const string & max_name); //prints all county names
//to the screen between min_name and max_name, inclusive.
void print_tree( );//prints each county record to the screen sorted by county name.
void sorted_info( );//prints each county record to a file called “county_info.txt” sorted by county
//name”.
private:
treenode *root;
};
3. Notes on implementation of county_ranges, sorted_info, and del_name are as follows:
a. The void member function “county_ranges” that accepts two values that represents a name
range and prints all the counties with a names in the range, inclusive. Consider the following
prototype and function call:
Prototype: void population_ranges(const double& min_name, const double & max_name);
Function Call: county_ranges(“bay”, “flager”);
b. 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( );
c. 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
d. 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”.
************************************************************************
/*
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
#include
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 *);
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
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;
}
************************************************************
//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: county_ranges ";
myTree.county_ranges("bbbb","k");
cout<<"End Test3 ";
cout<<"Test4: del_name ";
myTree.del_name("miami-dade");
myTree.print_tree();
cout<<"End Test4 ";
cout<<"Test5: sorted_info ";
myTree.sorted_info();
cout<<"End Test5 ";
return 0;
}
*****************************************************************************
county_data.txt
Lake 301019
Lafayette 8942
Lee 631330
Jefferson 14658
Leon 277971
Jackson 49292
Levy 40156
Indian River 138894
Liberty 8314
Holmes 19873
Madison 19115
Hillsborough 1267775
Manatee 327142
Highlands 98630
Marion 332529
Hernando 173094
Martin 147495
Hendry 39089
Miami-Dade 2662874
Hardee 27887
Monroe 73873
Hamilton 14671
Nassau 74195
Gulf 15844
Okaloosa 183482
Glades 12635
Okeechobee 40140
Gilchrist 17004
Orange 1169107
Gadsden 46151
Osceola 276163
Franklin 11596
Palm Beach 1335187
Flagler 97376
Pasco 466457
Escambia 299114
Pinellas 917398
Duval 870709
Polk 609492
Dixie 16486
Putnam 74041
DeSoto 34894
Santa Rosa 154104
Columbia 67485
Sarasota 38213
Collier 328134
Seminole 425071
Clay 192970
Citrus 140031
St. Johns 195823
Charlotte 160511
St. Lucie 280379
Calhoun 14750
Sumter 97756
Broward 1780172
Suwannee 41972
Brevard 543566
Taylor 22691
Bradford 28255
Union 15388
Bay 169856
Volusia 494804
Baker 27154
Wakulla 30978
Alachua 249365
Walton 55793
Washington 24935
Explanation / Answer
#include
#include
using namespace std;
//changing class tree node
class treenode
{
public:
string county_name;
double population_size;
treenode *lchild, *rchild; //left and right children pointers
};
//changing BST to bst
class bst
{
public:
//changing constructor BST to bst
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 item);
treenode * search_tree(treenode *, string item);
treenode * search_tree(string item);
treenode * inorder_succ(treenode *);
void print_tree();
void print_tree(treenode *);
private:
treenode *root;
};
bool bst::empty()
{
return (root == 0);
}
void bst::insert(string item)
{
insert(root, item);
}
void bst::insert(treenode * & loc_ptr, string item)
{
if (loc_ptr == 0)
{
loc_ptr = new treenode;
loc_ptr->lchild = loc_ptr->rchild = 0;
loc_ptr->country_name = item;
}
else if (loc_ptr->country_name>item)
insert(loc_ptr->lchild, item);
else if (loc_ptr->country_name
insert(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->country_name == item)
return loc_ptr;
else if (loc_ptr->country_name>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 item)
{
if (loc_ptr == 0)
cout << "item not in tree ";
else if (loc_ptr->country_name > item)
del_name(loc_ptr->lchild, item);
else if (loc_ptr->country_name < item)
del_name(loc_ptr->rchild, item);
else
{
treenode * ptr;
if (loc_ptr->lchild == 0)
{
ptr = loc_ptr->rchild;
del_nameete loc_ptr;
loc_ptr = ptr;
}
else if (loc_ptr->rchild == 0)
{
ptr = loc_ptr->lchild;
del_nameete loc_ptr;
loc_ptr = ptr;
}
else
{
ptr = inorder_succ(loc_ptr);
loc_ptr->country_name = ptr->country_name;
del_name(loc_ptr->rchild, ptr->country_name);
}
}
}
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->country_name << endl;
print_tree(loc_ptr->rchild);
}
}
bst::~bst()
{
while (root != 0)
{
del_name(root->country_name);
}
}
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=del_nameete 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 del_nameete: ";
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=del_nameete item,p=print tree, e=exit: ";
cin >> ch;
cout << endl;
}
cout << endl << "no more binary tree..... ";
return 0;
}
************************************************************
//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: county_ranges ";
myTree.county_ranges("bbbb","k");
cout<<"End Test3 ";
cout<<"Test4: del_name ";
myTree.del_name("miami-dade");
myTree.print_tree();
cout<<"End Test4 ";
cout<<"Test5: sorted_country_name ";
myTree.sorted_country_name();
cout<<"End Test5 ";
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.