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.