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

#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); } template void TreeType::optimalOrder(int arr[],int l,int r) { getOptimalOrder(arr,l,r,root); }

template void TreeType::getOptimalOrder(int arr[],int l,int r,TreeNode*& node) { if(l>r) return ;

int m = (l+r)/2; node = new TreeNode; node->right = NULL; node->left = NULL; node->info = arr[m]; cout<left); getOptimalOrder(arr,m+1,r,node->right);

}

#include "quetype.h"

template QueType::QueType(int max) { maxQue = max + 1; front = maxQue - 1; rear = maxQue - 1; items = new ItemType[maxQue]; } template QueType::QueType() { maxQue = 501; front = maxQue - 1; rear = maxQue - 1; items = new ItemType[maxQue]; } template QueType::~QueType() { delete [] items; } template void QueType::MakeEmpty() { front = maxQue - 1; rear = maxQue - 1; } template bool QueType::IsEmpty() { return (rear == front); } template bool QueType::IsFull() { return ((rear+1)%maxQue == front); } template void QueType::Enqueue(ItemType newItem) { if (IsFull()) throw FullQueue(); else { rear = (rear +1) % maxQue; items[rear] = newItem; } } template void QueType::Dequeue(ItemType& item) { if (IsEmpty()) throw EmptyQueue(); else { front = (front + 1) % maxQue; item = items[front]; } }

#ifndef QUETYPE_H_INCLUDED #define QUETYPE_H_INCLUDED

class FullQueue {}; class EmptyQueue {}; template class QueType { public: QueType(); QueType(int max); ~QueType(); void MakeEmpty(); bool IsEmpty(); bool IsFull(); void Enqueue(ItemType); void Dequeue(ItemType&); private: int front; int rear; ItemType* items; int maxQue; };

#endif // QUETYPE_H_INCLUDED

Question: An unsorted array containing tree keys is given. Build a balanced BST (Binary Search Tree) from it.

Input: keys = [8, 3, 10, 1, 6, 14, 4, 7, 13]

do it within 15 minutes