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\n";
}
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\n";
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\n";
else
cout << s << " was found in the tree\n";
break;
case 'd':cout << "enter word to delete: ";
cin >> s;
B.del(s);
break;
case 'p':cout << "...printing tree...\n";
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.....\n";
return 0;
}
************************************************************
//Sample driver. Make correction and changes as necessary
int main( )
{
cout<<"Test1: default constructor\n";
bst myTree;
myTree.print_tree();
cout<<"End Test1\n";
cout<<"Test2:insert\n";
myTree.insert("new-county", 234658);
myTree.print_tree();
cout<<"End Test2\n";
cout<<"Test3: county_ranges\n";
myTree.county_ranges("bbbb","k");
cout<<"End Test3\n";
cout<<"Test4: del_name\n";
myTree.del_name("miami-dade");
myTree.print_tree();
cout<<"End Test4\n";
cout<<"Test5: sorted_info\n";
myTree.sorted_info();
cout<<"End Test5\n";
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
#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\n";
}
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\n";
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\n";
else
cout << s << " was found in the tree\n";
break;
case 'd':cout << "enter word to del_nameete: ";
cin >> s;
B.del_name(s);
break;
case 'p':cout << "...printing tree...\n";
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.....\n";
return 0;
}
************************************************************
//Sample driver. Make correction and changes as necessary
int main( )
{
cout<<"Test1: default constructor\n";
bst myTree;
myTree.print_tree();
cout<<"End Test1\n";
cout<<"Test2:insert\n";
myTree.insert("new-county", 234658);
myTree.print_tree();
cout<<"End Test2\n";
cout<<"Test3: county_ranges\n";
myTree.county_ranges("bbbb","k");
cout<<"End Test3\n";
cout<<"Test4: del_name\n";
myTree.del_name("miami-dade");
myTree.print_tree();
cout<<"End Test4\n";
cout<<"Test5: sorted_country_name\n";
myTree.sorted_country_name();
cout<<"End Test5\n";
return 0;
}
Name the program for this assignment "bst_driver.cpp." In this assignment you will make several modifications to...
C++ EXERCISE (DATA STRUCTURES). I just need a code for some functions that are missing. Please help me figure out. Thanks. C++ BST implementation (using a struct) Enter the code below, and then compile and run the program. After the program runs successfully, add the following functions: postorder() This function is similar to the inorder() and preorder() functions, but demonstrates postorder tree traversal. displayParentsWithTwo() This function is similar to the displayParents WithOne() function, but displays nodes having only two children....
Hi there, I am working on a binary search tree code in c++. The program must store and update students' academic records, each node includes the student name, credits attempted, credits earned and GPA. I have made some progress with the code and written most of the functions in the .cpp file (already did the .h file) but i am struggling with what to put in the main and how to put an update part in the insert function. I...
Write a function, swapSubtrees, that swaps all of the left and right subtrees of a binary tree. Add this function to the class binaryTreeType and create a program to test this function. #include <iostream> using namespace std; //Definition of the Node template <class elemType> struct nodeType { elemType info; nodeType<elemType> *lLink; nodeType<elemType> *rLink; }; //Definition of the class template <class elemType> class binaryTreeType { public: //Overload the assignment operator. const binaryTreeType<elemType>& operator=(const binaryTreeType<elemType>&) { if (this != &otherTree) //avoid self-copy...
Given the following code: #ifndef TREE_H #define TREE_H #include <iostream> #include "TreeNode.h" template< typename NODETYPE > class Tree { public: Tree() : rootPtr( nullptr ) {} void insertNode( const NODETYPE &value ) { insertNodeHelper( &rootPtr, value ); } void preOrderTraversal() const { preOrderHelper( rootPtr ); } void inOrderTraversal() const { inOrderHelper( rootPtr ); } private: TreeNode< NODETYPE > *rootPtr; void insertNodeHelper( TreeNode< NODETYPE > **ptr, const NODETYPE &value ) { if ( *ptr == nullptr ) * ptr = new...
I need to make it so this program outputs to an output.txt, the program works fine, just need it to fprintf to output.txt #include <stdio.h> #include <string.h> #include <malloc.h> #define MAX 30 struct treeNode { char names[MAX]; struct treeNode *right; struct treeNode *left; }*node; void searchName(char names[], struct treeNode ** parent, struct treeNode ** location) { struct treeNode * ptr, * tempPtr; if(node == NULL) { *location = NULL; *parent = NULL; return; } if(strcmp(names, node->names) == 0)...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to completely test every method in the BST class to ensure the class meets all its requirements. You should read the Listing 25.5: TestBST.java for an idea of what your program should look like. Listing 25.4 BST.java public class BST> extends AbstractTree { protected TreeNode...
write a new test program called RemoveDuplicates.java. The program reads text input from keyboard or a text file and adds the words to a BST. The program then traverses the BST and prints out the words in order (based on ASCII/UNICODE order) on the screen (or to output text file). Note that you may need to make some changes to BST.java. Sample test: ----jGRASP exec: java -ea removeDuplicates Original Text: a B 2 n w C q K l 0...
For this computer assignment, you are to write a C++ program to implement a class for binary trees. To deal with variety of data types, implement this class as a template. The definition of the class for a binary tree (as a template) is given as follows: template < class T > class binTree { public: binTree ( ); // default constructor unsigned height ( ) const; // returns height of tree virtual void insert ( const T& ); //...
Write a C++ program to validate computer user-ids and passwords. A list of valid ids and passwords (unsorted) is read from a file and stored in a Binary Search Tree (BST) of UserInfo objects. When user-ids and passwords are entered during execution, this BST is searched to determine whether they are legal. Input (file): UserInfo records for valid users Input (keyboard): Ids and passwords of users logging in Output (screen): Messages indicating whether user-ids and passwords are valid, as well...
Take the following code for a binary source tree and make it include the following operations. bool replace(const Comparable & item, const Comparable & replacementItem); int getNumberOfNodes() const; (a) The replace method searches for the node that contains item in a binary search tree, if it is found, it replaces item with replacementItem. The binary tree should remain as a binary search tree after the replacement is done. Add the replace operation to the BinarySearchTree class. Test your replace using...