After completing this assignment you will be able to implement a binary search t

Question

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: 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”. Please submit your files in a zip file called “module11.zip” before the due date and time. Please start early, and let me know if you have any questions.

Explanation / Answer

#include "BinarySearchTree.h"

#include "BinaryTreeIterator.h"

#include "ListArray.h"

using CSC2110::ListArray;

#include "ListArrayIterator.h"

using CSC2110::ListArrayIterator;

#include "CD.h"

using CSC2110::CD;

#include <iostream>

using namespace std;

void deleteCDs(ListArray<CD>* list)

{

ListArrayIterator<CD>* iter = list->iterator();

while(iter->hasNext())

{

CD* cd = iter->next();

delete cd;

}

delete iter;

}

int main()

{

//the unsorted ListArray of cds

ListArray<CD>* cds = CD::readCDs("cds.txt");

int numItems = cds->size();

cout << numItems << endl;

cout << endl;

//test the binary search tree

//insert all of the cds

ListArrayIterator<CD>* iter = cds->iterator();

BinarySearchTree<CD>* bst = new BinarySearchTree<CD>(&CD::compare_items, &CD::compare_keys);

while(iter->hasNext())

{

CD* cd = iter->next();

bst->insert(cd);

}

delete iter;

BinaryTreeIterator<CD>* bst_iter = bst->iterator();

bst_iter->setInorder(); //takes a snapshot of the data

while(bst_iter->hasNext())

{

CD* cd = bst_iter->next();

cd->displayCD();

}

delete bst_iter;

//DO THIS

//display the height of the binary search tree (not minimum height)

//display whether the binary search tree is balanced (should not be balanced)

int height = bst->getHeight();

cout << "The height of the tree is: " << height << endl << endl;

bool balanceAbility = bst->isBalanced();

if(balanceAbility == true)

{

cout << "The tree is balanced. ";

}

else

{

cout << "The tree is not balanced. ";

}

//create a minimum height binary search tree

BinarySearchTree<CD>* min_bst = bst->minimize();

bst_iter = min_bst->iterator();

//make sure that an inorder traversal gives sorted order

bst_iter->setInorder(); //takes a snapshot of the data

while(bst_iter->hasNext())

{

CD* cd = bst_iter->next();

cd->displayCD();

}

delete bst_iter;

//DO THIS

//display the height of the binary search tree (should be minimum height)

//display whether the binary search tree is balanced (should be balanced)

height = min_bst->getHeight();

cout << "The height of the tree is: " << height << endl << endl;

balanceAbility = min_bst->isBalanced();

if(balanceAbility == true)

{

cout << "The tree is balanced ";

}

else

{

cout << "The tree is not balanced. ";

}

//create a complete binary search tree

BinarySearchTree<CD>* complete_bst = bst->minimizeComplete();

delete bst;

//make sure that an inorder traversal gives sorted order

bst_iter = complete_bst->iterator();

bst_iter->setInorder(); //takes a snapshot of the data

while(bst_iter->hasNext())

{

CD* cd = bst_iter->next();

cd->displayCD();

}

delete bst_iter;

//DO THIS

//display the height of the complete binary search tree (should be minimum height)

//display whether the binary search tree is balanced (should be balanced)

height = complete_bst->getHeight();

cout << "The height of the tree is: " << height << endl << endl;

balanceAbility = complete_bst->isBalanced();

if(balanceAbility == true)

{

cout << "The tree is balanced. ";

}

else

{

cout << "The tree is not balanced. ";

}

delete complete_bst;

deleteCDs(cds);

delete cds;

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.