urgent please. just add the function to binarysearchtree.cpp and in driver file run the function. all codes are given bellow.
Modify the implementation of binary search tree and add a function to count the number of leaf nodes.
Modify the implementation of binary search tree and add a function to calculate the height of the tree.
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 < tree->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 < tree->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 < tree->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 << tree->info << " "; PrintTree(tree->right); } } template void TreeType::Print() { PrintTree(root); }
main function:
#include #include "binarysearchtree.h" #include "binarysearchtree.cpp" #include "QueType.h" using namespace std;
void checkEmpty(bool b){ if(b) cout << "Tree is Empty" << endl; else cout << "Tree is not Empty" << endl; } void BST_withMinimumHeight(TreeType& bstMinimumHeight, int arr[], int start, int end) { if (start > end) return; int mid = (start + end)/2; cout< tree; checkEmpty(tree.IsEmpty()); tree.InsertItem(4); tree.InsertItem(9); tree.InsertItem(2); tree.InsertItem(7); tree.InsertItem(3); tree.InsertItem(11); tree.InsertItem(17); tree.InsertItem(0); tree.InsertItem(5); tree.InsertItem(1); checkEmpty(tree.IsEmpty()); cout << tree.LengthIs() << endl; bool b;int v=9; tree.RetrieveItem(v,b); if(b) cout << "Item is found" << endl; else cout << "Item is not found" << endl; v=13; tree.RetrieveItem(v,b); if(b) cout << "Item is found" << endl; else cout << "Item is not found" << endl;
tree.ResetTree(IN_ORDER); bool finish = 0; while(!finish){ int value; tree.GetNextItem(value,IN_ORDER,finish); cout << value <<" "; } cout << endl; tree.ResetTree(PRE_ORDER); finish = 0; while(!finish){ int value; tree.GetNextItem(value,PRE_ORDER,finish); cout << value <<" "; } cout << endl; tree.ResetTree(POST_ORDER); finish = 0; while(!finish){ int value; tree.GetNextItem(value,POST_ORDER,finish); cout << value <<" "; } cout << endl; tree.MakeEmpty(); checkEmpty(tree.IsEmpty());
TreeType bstMinimumHeight; int arr[] = {11, 9, 4, 2, 7, 3, 17, 0, 5, 1}; int n = sizeof(arr) / sizeof(arr[0]); BST_withMinimumHeight(bstMinimumHeight, arr, 0, n-1); cout << endl; return 0; }
