Follow the instructions:

you can change the .cpp files if needed. BST's header and .cpp file is given below .(if you change the .cpp file please submit the header and .cpp file also)

your task is :-

1. Write a function to calculate the number of leaves a tree has. For the given tree the expected output is 5. 2. Write a function to print the elements so that the expected output is: 10, 14, 2, 12, 25, 75, 8, 50, 15.

PLEASE don't copy incorrect answers that already exist in Chegg, use the materials to complete the tasks. thank you.

binarysearchtree.h

#ifndef BINARYSEARCHTREE_H_INCLUDED #define BINARYSEARCHTREE_H_INCLUDED #include "quetype.h" template struct TreeNode { ItemType info; TreeNode* left; TreeNode* right; }; enum OrderType {PRE_ORDER, IN_ORDER, POST_ORDER}; template class TreeType { public: TreeType(); ~TreeType(); void MakeEmpty(); bool IsEmpty(); bool IsFull(); int LengthIs(); void RetrieveItem(ItemType& item, bool& found); void InsertItem(ItemType item); void DeleteItem(ItemType item); void ResetTree(OrderType order); void GetNextItem(ItemType& item, OrderType order, bool& finished); void Print(); private: TreeNode* root; QueType preQue; QueType inQue; QueType postQue; }; #endif // BINARYSEARCHTREE_H_INCLUDED

binarysearchtree.cpp

#include "binarysearchtree.h" #include "quetype.cpp" #include using namespace std; template TreeType::TreeType() { root = NULL; } template void Destroy(TreeNode*& tree) { if (tree != NULL) { Destroy(tree->left); Destroy(tree->right); delete tree; tree = NULL; } } template TreeType::~TreeType() { Destroy(root); } template void TreeType::MakeEmpty() { Destroy(root); } template bool TreeType::IsEmpty() { return root == NULL; } 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 == NULL) 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 == NULL) 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 void TreeType::RetrieveItem(ItemType& item, bool& found) { Retrieve(root, item, found); }

template void Insert(TreeNode*& tree, ItemType item) { if (tree == NULL) { tree = new TreeNode; tree->right = NULL; tree->left = NULL; tree->info = item; } else if (item info) Insert(tree->left, item); else Insert(tree->right, item); } template void TreeType::InsertItem(ItemType item) { Insert(root, item); } template void Delete(TreeNode*& tree, ItemType item) { if (item info) Delete(tree->left, item); else if (item > tree->info) Delete(tree->right, item); else DeleteNode(tree); } template void DeleteNode(TreeNode*& tree) { ItemType data; TreeNode* tempPtr; tempPtr = tree; if (tree->left == NULL) { tree = tree->right; delete tempPtr; } else if (tree->right == NULL) { tree = tree->left; delete tempPtr; } else { GetPredecessor(tree->left, data); tree->info = data; Delete(tree->left, data); } } template void GetPredecessor(TreeNode* tree, ItemType& data) { while (tree->right != NULL) tree = tree->right; data = tree->info; } template void TreeType::DeleteItem(ItemType item) { Delete(root, item); } template void PreOrder(TreeNode* tree, QueType& Que) { if (tree != NULL) { Que.Enqueue(tree->info); PreOrder(tree->left, Que); PreOrder(tree->right, Que); } } template void InOrder(TreeNode* tree, QueType& Que) { if (tree != NULL) { InOrder(tree->left, Que); Que.Enqueue(tree->info); InOrder(tree->right, Que); } } template void PostOrder(TreeNode* tree, QueType& Que) { if (tree != NULL) { PostOrder(tree->left, Que); PostOrder(tree->right, Que); Que.Enqueue(tree->info); } } template void TreeType::ResetTree(OrderType order) { switch (order) { case PRE_ORDER: PreOrder(root, preQue); break; case IN_ORDER: InOrder(root, inQue); break; case POST_ORDER: PostOrder(root, postQue); break; } } template void TreeType::GetNextItem(ItemType& item, OrderType order, bool& finished) { finished = false; switch (order) { case PRE_ORDER: preQue.Dequeue(item); if(preQue.IsEmpty()) finished = true; break; case IN_ORDER: inQue.Dequeue(item); if(inQue.IsEmpty()) finished = true; break; case POST_ORDER: postQue.Dequeue(item); if(postQue.IsEmpty()) finished = true; break; } }

template void PrintTree(TreeNode* tree) { if (tree != NULL) { PrintTree(tree->left); cout info right); } } template void TreeType::Print() { PrintTree(root); }

quetype.h #ifndef QUETYPE_H_INCLUDED #define QUETYPE_H_INCLUDED class FullQueue {}; class EmptyQueue {}; template class QueType { struct NodeType { ItemType info; NodeType* next; }; public: QueType(); ~QueType(); void MakeEmpty(); void Enqueue(ItemType); void Dequeue(ItemType&); bool IsEmpty(); bool IsFull(); private: NodeType *front, *rear; }; #endif // QUETYPE_H_INCLUDED

quetype.cpp #include "quetype.h" #include using namespace std; template QueType::QueType() { front = NULL; rear = NULL; } template bool QueType::IsEmpty() { return (front == NULL); } template bool QueType::IsFull() { NodeType* location; try { location = new NodeType; delete location; return false; } catch(bad_alloc& exception) { return true; } } template void QueType::Enqueue(ItemType newItem) { if (IsFull()) throw FullQueue(); else { NodeType* newNode; newNode = new NodeType; newNode->info = newItem; newNode->next = NULL; if (rear == NULL) front = newNode; else rear->next = newNode; rear = newNode; } } template void QueType::Dequeue(ItemType& item) { if (IsEmpty()) throw EmptyQueue(); else { NodeType* tempPtr; tempPtr = front; item = front->info; front = front->next; if (front == NULL) rear = NULL; delete tempPtr; } } template void QueType::MakeEmpty() { NodeType* tempPtr; while (front != NULL) { tempPtr = front; front = front->next; delete tempPtr; } rear = NULL; } template QueType::~QueType() { MakeEmpty(); }

Task 03 (15pts + 15pts] Examine the binary tree in figure: 02, and solve the following problems: 15 50 12 25 75 10 14 Figure 2: Binary Tree 1. Write a function to calculate the number of leaves a tree has. For the given tree the expected output is 5. 2. Write a function to print the elements so that the expected output is: 10, 14, 2, 12, 25, 75, 8, 50, 15