Question
Please solve this problem with C++ with .cpp and .h fileand show every step clearly. //main #include #include BinarySearchTree.h #include using namespace std; int main()
Please solve this problem with C++ with .cpp and .h fileand show every step clearly.
//main #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.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; }
//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
Gdrive Link : https://drive.google.com/file/d/1TG_hfHkap6FO7El5ZVOVQR-iohF0gGDJ/view?usp=sharing
Modify the TreeType class (Binary Search Tree) such that no duplicate value can be inserted. In the driver file: a. Create an integer TreeType object. b. Insert some items c. Print the tree in InOrder. Modify the TreeType class (Binary Search Tree) such that no duplicate value can be inserted. In the driver file: a. Create an integer TreeType object. b. Insert some items c. Print the tree in InOrderStep by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started