Total Points: 25 After completing this assignment yo l be able to implement a bi
ID: 3919075 • Letter: T
Question
Total Points: 25 After completing this assignment yo l 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; ouble population_size; treenode Ichild, "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 fabove; 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; I) change name of "print_tree aux" to "print tree". m) leave private area (the state) as is;Explanation / Answer
#include <iostream>
template <class T>
class Tree
{
struct TreeNode
{
T data;
TreeNode * left;
TreeNode * right;
TreeNode(T val):data(val),left(NULL),right(NULL)
{
}
};
TreeNode * root;
void print(TreeNode*);
void freeMemory(TreeNode*);
public:
Tree();
~Tree();
void insert(T);
void print();
};
template <class T>
Tree<T>::Tree():root(NULL){}
template <class T>
Tree<T>::~Tree()
{
freeMemory(root);
}
template <class T>
void Tree<T>::freeMemory(Tree::TreeNode *node)
{
if (node==NULL)
return;
if (node->left)
freeMemory(node->left);
if (root->right)
freeMemory(node->right);
delete node;
}
template <class T>
void Tree<T>::insert(T val)
{
TreeNode * treeNode = NULL;
try
{
treeNode = new TreeNode(val);
} catch (std::bad_alloc &exception)
{
std::cerr << "bad_alloc caught: " << exception.what() << std::endl;
EXIT_FAILURE;
}
TreeNode *temp=NULL;
TreeNode *prev=NULL;
temp = root;
while(temp)
{
prev = temp;
if (temp->data < treeNode->data)
temp = temp->right;
else
temp = temp->left;
}
if (prev==NULL)
root = treeNode;
else
{
if (prev->data<treeNode->data)
prev->right = treeNode;
else
prev->left = treeNode;
}
}
template <class T>
void Tree<T>::print(TreeNode *root)
{
if (root==NULL)
return ;
print(root->left);
std::cout << root->data << std::endl;
print(root->right);
}
template <class T>
void Tree<T>::print()
{
print(root);
}
int main()
{
Tree<int> tree;
tree.insert(14);
tree.insert(12);
tree.insert(6);
tree.insert(17);
tree.insert(8);
tree.print();
}
Output:
6
8
12
14
17