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(Header file) 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.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; }
4. Bonus Task: Remember the implementations of SortedList data structures? So far, we have implemented array based and linked list based SortedList 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. Need hints? Check the class recording of the last class. 4. Bonus Task: Remember the implementations of SortedList data structures? So far, we have implemented array based and linked list based SortedList 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. Need hints? Check the class recording of the last class
