Please solve this problem with C++ and show every step clearly. It contain

1. Driver file

2. header file

3. Implementation file

When you give me the answer pls add your screen short with output window.

Now, I am attaching the function which are related to question. Please check and modify

//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; }

//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; }

4. Bonus Task: Remember the implementations of Sorted List data structures? So far, we have implemented array based and linked list based Sorted List data structure. Your job for this task is to implement a binary search tree based Sorted List data structure. In the driver file: a. Create an integer Sorted List object. b. Insert some items. c. Print the list. All of the function prototypes for your SortedList class functions must be the same as they are for the linked list based Sorted List class. 4. Bonus Task: Remember the implementations of Sorted List data structures? So far, we have implemented array based and linked list based Sorted List data structure. Your job for this task is to implement a binary search tree based Sorted List data structure. In the driver file: a. Create an integer Sorted List object. b. Insert some items. c. Print the list. All of the function prototypes for your SortedList class functions must be the same as they are for the linked list based Sorted List class