Name the program for this assignment \"bst_driver.cpp.\" In this assignment you
ID: 3698131 • 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) add “del_population”; i) add “del_population” with a different signature than h above; j) leave “search_tree” as is; k) change name of “search_tree_aux” to “search_tree”; l) leave “inorder_succ” as is; m) leave “print_tree” as is; n) change name of “print_tree_aux” to “print_tree”. o) leave private area (the state) as is; p) 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; }; 3. Notes on implementation of population_ranges, sorted_info, del_population, and del_name are as follows: a. 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); 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_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. d. 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. e. 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 f. 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.
bst_driver.cpp
county_data.txt
Explanation / Answer
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
//Class declaration for Binary seach tree
class StringbinarysearchTree{
private:
class TreeNode{
friend class StringTree;
string str;
TreeNode *left;
TreeNode *right;
TreeNode(string s, TreeNode *l=NULL, TreeNode *r=NULL){
str=s, left=l, right=r;}
};
TreeNode *root;
void insertelement(TreeNode *&tree, string word);
void removeelement(TreeNode *&tree, string word);
void makeDeletionhere(TreeNode *&tree);
void destroySubtreehere(TreeNode *tree);
void displayInOrdertraversal(TreeNode *tree);
void displayPreOrdertraversal(TreeNode *tree);
void displayPostOrdertraversal(TreeNode *tree);
public:
//inline recursive functions
StringbinarysearchTree()
{root=NULL;}
~StringbinarysearchTree()
{destroySubtree(root);}
bool search(string word);
bool isBalanced(TreeNode *tree);
int height(TreeNode *tree);
void insertelement(string word)
{insertelement(root, word);}
void removeelement(string word)
{removeelement(root, word);}
void showInOrder(void)
{displayInOrdertraversal(root);}
void showPreOrder(void)
{displayPreOrder(root);}
void showPostOrder(void)
{displayPostOrdertraversal(root);}
void getTreeSize (int &size);
};
//This is used for inserting into the tree
void StringbinarysearchTree::insertelement(TreeNode *&tree, string word)
{
if(!tree)
{tree=new TreeNode(word);
return;}
if(tree->str.compare(word))
return;
if(tree->str.compare(word)<0)
insert(tree->left, word);
else
insert(tree->right, word);
}
//rThis function is used for removing from the tree
void StringbinarysearchTree::removeelement(TreeNode *&tree, string word)
{
if(!tree) return;
if(tree->str.compare(word)<0)
remove(tree->left, word);
else if(tree->str.compare(word)>0)
remove(tree->right, word);
else
makeDeletion(tree);
}
//This function is used for searching for data in the tree
bool StringbinarysearchTree::search(string word)
{
TreeNode *tree=root;
while(tree){
if(tree->str.compare(word))
return true;
else if(tree->str.compare(word)<0)
tree=tree->left;
else
tree=tree->right;
}
return false;
}
// destroys a subtree
void StringbinarysearchTree::destroySubtree(TreeNode *tree){
if(!tree) return;
destroySubtree(tree->left);
destroySubtree(tree->right);
delete tree;
}
//This functions prints using inorder method
void StringbinarysearchTree::displayInOrdertraversal(TreeNode *tree){
if(tree){
displayInOrder(tree->left);
cout<<tree->str<<" ";
displayInOrder(tree->right);
}
}
//This function prints using preorder method
void StringbinarysearchTree::displayPreOrdertraversal(TreeNode *tree){
if(tree){
cout<<tree->str<<" ";
displayPreOrder(tree->left);
displayPreOrder(tree->right);
}
}
//This functionprints using post order method
void StringbinarysearchTree::displayPostOrdertraversal(TreeNode *tree){
if(tree){
displayPostOrder(tree->left);
displayPostOrder(tree->right);
cout<<(tree->str)<<" ";
}
}
//for deleting
void StringbinarsearchTree::makeDeletionhere(TreeNode *&tree){
TreeNode *deleteNode;
TreeNode *attach;
if(!tree->right)
tree=tree->left;
else if(!tree->left)
tree=tree->right;
else
attach=tree->right;
while(attach->left)
{
attach=attach->left;
attach->left=tree->left;
tree=tree->right;
}
delete deleteNode;
}
void StringbinarysearchTree::getTreeSize (int &size)
{
TreeNode *tree=root;
while(tree){
if (tree->right)
{
size++;
tree=tree->right;
}
if (tree->left)
{
size++;
tree=tree->left;
}
}
}//end getTreeSize
bool StringTree::isBalanced(TreeNode *tree)
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */
/* If tree is empty then return true */
if(!tree)
return 1;
/* Get the height of left and right sub trees */
lh = height(tree->left);
rh = height(tree->right);
if( abs(lh-rh) <= 1 &&
isBalanced(root->left) &&
isBalanced(root->right))
return 1;
/* If we reach here then tree is not balanced */
return 0;
}//end isBalanced
int StringTree::height(TreeNode *tree)
{
if (!tree)
return 0;
else
{
/* now we will be computing the depth of each subtree */
int lDepth = height(tree->left);
int rDepth = height(tree->right);
/* use the larger one */
if (lDepth > rDepth)
return (lDepth+1);
else return (rDepth+1);
}
}
}
it is fast and insertion and deletion takes place easily when the tree is balanced.
disadvantages:
searching takes longer time as shape of tree depends on insertions.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.