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