Solve the problem using C++. Make necessary changes in the following codes to complete the task. Here I am unable to attach the queue class code as it is showing too large. Please manage

BinarySearchTree.h

#ifndef BINARYSEARCHTREE_H_INCLUDED #define BINARYSEARCHTREE_H_INCLUDED #include "Queue.h"

enum OrderType {PRE_ORDER, IN_ORDER, POST_ORDER};

template struct TreeNode { ItemType info; TreeNode* left; TreeNode* right; };

template class TreeType { public: TreeType(); // done ~TreeType(); void MakeEmpty();

bool IsEmpty(); // d bool IsFull(); // d int LengthIs(); //d

bool InsertItem(ItemType item); // d bool DeleteItem(ItemType item); // d bool RetrieveItem(ItemType& item); //d

void ResetTree(OrderType order); // bool GetNextItem(ItemType& item, OrderType order);

private: TreeNode* root; Queue preQue; Queue inQue; Queue postQue; }; #include "BinarySearchTree.tpp" #endif // BINARYSEARCHTREE_H_INCLUDED

BinarySearchTree.tpp

#include "BinarySearchTree.h" #include

using namespace std; template TreeType::TreeType() { root = nullptr; }

template void Destroy(TreeNode*& tree) { if (tree != nullptr) { Destroy(tree->left); Destroy(tree->right); delete tree; tree = nullptr; } }

template TreeType::~TreeType() { Destroy(root); }

template void TreeType::MakeEmpty() { Destroy(root); }

template bool TreeType::IsEmpty() { return (root == nullptr); }

template bool TreeType::IsFull() { TreeNode* location; try { location = new TreeNode; delete location; return false; } catch(bad_alloc& exception) { return true; } }

template int CountNodes(TreeNode* tree) { if (tree == nullptr) return 0; else return CountNodes(tree->left) + CountNodes(tree->right) + 1; }

template int TreeType::LengthIs() { return CountNodes(root); }

template void Retrieve(TreeNode* tree, ItemType& item, bool& found) { if (tree == nullptr) found = false; else if (item info) Retrieve(tree->left, item, found); else if (item > tree->info) Retrieve(tree->right, item, found); else { item = tree->info; found = true; } }

template bool TreeType::RetrieveItem(ItemType& item) { bool found; Retrieve(root, item, found); return found; }

template void Insert(TreeNode*& tree, ItemType item) { // reference of a treenode pointer variable if (tree == nullptr) { tree = new TreeNode; tree->right = nullptr; tree->left = nullptr; tree->info = item; } else if (item info) Insert(tree->left, item); else Insert(tree->right, item); }

template bool TreeType::InsertItem(ItemType item) { if(IsFull()){ return false; } Insert(root, item); return true; }

template void GetPredecessor(TreeNode* tree, ItemType& data) { while (tree->right != nullptr) tree = tree->right; data = tree->info; }

template void DeleteNode(TreeNode*& tree) { TreeNode* tempPtr; tempPtr = tree; if (tree->left == nullptr) { tree = tree->right; delete tempPtr; } else if (tree->right == nullptr) { tree = tree->left; delete tempPtr; } else { ItemType data; GetPredecessor(tree->left, data); tree->info = data; Delete(tree->left, data); } }

template bool Delete(TreeNode*& tree, ItemType item) { if (tree == nullptr) return false; if (item info) return Delete(tree->left, item); else if (item > tree->info) return Delete(tree->right, item); else { DeleteNode(tree); return true; } }

template bool TreeType::DeleteItem(ItemType item) { return Delete(root, item); }

template void PreOrder(TreeNode* tree, Queue& Que) { if (tree != nullptr) { Que.EnQueue(tree->info); PreOrder(tree->left, Que); PreOrder(tree->right, Que); } }

template void InOrder(TreeNode* tree, Queue& Que) { if (tree != nullptr) { InOrder(tree->left, Que); Que.EnQueue(tree->info); InOrder(tree->right, Que); } }

template void PostOrder(TreeNode* tree, Queue& Que) { if (tree != nullptr) { PostOrder(tree->left, Que); PostOrder(tree->right, Que); Que.EnQueue(tree->info); } }

template void TreeType::ResetTree(OrderType order) { switch (order) { case PRE_ORDER: preQue.MakeEmpty(); PreOrder(root, preQue); break; case IN_ORDER: inQue.MakeEmpty(); InOrder(root, inQue); break; case POST_ORDER: postQue.MakeEmpty(); PostOrder(root, postQue); break; } }

template bool TreeType::GetNextItem(ItemType& item, OrderType order) { switch (order) { case PRE_ORDER: if(preQue.IsEmpty()) return false; item = preQue.GetFront(); preQue.DeQueue(); break; case IN_ORDER: if(inQue.IsEmpty()) return false; item = inQue.GetFront(); inQue.DeQueue(); break; case POST_ORDER: if(postQue.IsEmpty()) return false; item = postQue.GetFront(); postQue.DeQueue(); break; } return true; }

Queue.h

#ifndef QUEUE_H #define QUEUE_H

class FullQueue{}; class EmptyQueue{};

//using namespace std; template class Queue{ struct Node{ ItemType info; Node* next; };

private: Node* front; Node* rear;

public: Queue(); ~Queue();

void EnQueue(ItemType); void DeQueue(); ItemType GetFront(); void MakeEmpty();

bool IsEmpty(); bool IsFull(); };

#include "Queue.tpp" #endif

Queue.tpp

template Queue::Queue() { front = nullptr; rear = nullptr; }

template void Queue::EnQueue(ItemType item) { if(IsFull()) throw FullQueue();

Node* newNode = new Node; newNode->info = item; newNode->next = nullptr;

if(IsEmpty()) front = newNode; else rear->next = newNode;

rear = newNode; }

template void Queue::DeQueue() { //void Queue::Dequeue(ItemType& item) { if(IsEmpty()) throw EmptyQueue();

//item = front->info;

Node* temp = front; front = front->next;

if(front == nullptr) rear = nullptr;

delete temp;

}

template ItemType Queue::GetFront() { if(IsEmpty()) throw EmptyQueue();

return front->info; }

template void Queue::MakeEmpty() {

/*Node* temp; while (front != nullptr){ temp = front; front = front->next; delete temp; } rear = nullptr;*/

while(!IsEmpty()) DeQueue(); }

template bool Queue::IsEmpty() { return (front == nullptr); }

template bool Queue::IsFull() { try { Node *temp = new Node; delete temp; return false; } catch (std::bad_alloc& e) { return true; } }

template Queue::~Queue(){ MakeEmpty(); }

main.cpp

#include #include "BinarySearchTree.h" #include using namespace std;

int main() {

TreeType x;

x.InsertItem(10); x.InsertItem(5); x.InsertItem(2); x.InsertItem(7); x.InsertItem(15); x.InsertItem(12); x.InsertItem(20);

x.ResetTree(IN_ORDER);

int out=0; while(x.GetNextItem(out,IN_ORDER)){ cout

cout

/*while(!x.inQue.IsEmpty()){ cout

if(!x.DeleteItem(0)) cout

cout

x.ResetTree(IN_ORDER);

out=0; while(x.GetNextItem(out,IN_ORDER)){ cout

if(x.RetrieveItem(out)){ cout

x.MakeEmpty(); if(x.IsEmpty()){ cout

cout

return 0; }

2. Create a public function with function prototype int getHeight();" in the Tree Type class (Binary Search Tree) that returns the size of the tree. In the driver file: a. Create an integer TreeType object. b. Insert some items c. Print the height of the tree