implemantation With C++ please.

8.35 - The prototype declarations for MakeTree and AddElements (which is called by MakeTree and recursively calls itself to add elements from the array into the BST) appear below:

void MakeTree(TreeType tree&, int info[], int length);

void AddElements(TreeType tree&, int info[], int toIndex, int fromIndex);

Use the following sorted list as input to test your MakeTree() client function. After the BST has been created, call PrintTree() to dump the contents of the tree in (hopefully) sorted order:

-1000, -967, -923, -844, -669, -567, -455, -267, -209, -183, -59, -23, 68, 132, 159, 170, 222, 228, 233, 241, 389, 479, 824, 939, 985

Code:

//////////////////////////////////////////////////////////////////////////////////

//TreeType.h

//////////////////////////////////////////////////////////////////////////////////////////

#include #include

//template #include "QueType.h"

typedef char ItemType; struct TreeNode;

enum OrderType {PRE_ORDER, IN_ORDER, POST_ORDER};

class TreeType { public: TreeType(); // constructor ~TreeType(); // destructor TreeType(const TreeType& originalTree); void operator=(const TreeType& originalTree); // copy constructor void MakeEmpty(); bool IsEmpty() const; bool IsFull() const; int GetLength() const; ItemType GetItem(ItemType item, bool& found); void PutItem(ItemType item); void DeleteItem(ItemType item); void ResetTree(OrderType order); ItemType GetNextItem(OrderType order, bool& finished); void Print(std::ofstream& outFile) const; void Ancestors(ItemType item,std::ofstream& outFile); bool printAncestors(TreeNode *root,ItemType item,std::ofstream& outFile) const; TreeNode *roo() const { return root; } private: TreeNode* root; QueType preQue; QueType inQue; QueType postQue;

};

//////////////////////////////////////////////////////////////////////////////////////////////////////////////

//TreeType.cpp

////////////////////////////////////////////////////////////////////////////////////////////////////////////////// #include "TreeType.h" #include #include #include

using namespace std; struct TreeNode { ItemType info; TreeNode* left; TreeNode* right;

};

bool TreeType::IsFull() const // Returns true if there is no room for another item // on the free store; false otherwise. { TreeNode* location; try { location = new TreeNode; delete location; return false; } catch(std::bad_alloc exception) { return true; } }

bool TreeType::IsEmpty() const // Returns true if the tree is empty; false otherwise. { return root == NULL;

}

int CountNodes(TreeNode* tree);

int TreeType::GetLength() const // Calls recursive function CountNodes to count the // nodes in the tree. { return CountNodes(root); }

int CountNodes(TreeNode* tree) // Post: returns the number of nodes in the tree. { if (tree == NULL) return 0; else return CountNodes(tree->left) + CountNodes(tree->right) + 1; }

void Retrieve(TreeNode* tree, ItemType& item, bool& found);

ItemType TreeType::GetItem(ItemType item, bool& found) // Calls recursive function Retrieve to search the tree for item. { Retrieve(root, item, found); return item; }

void Retrieve(TreeNode* tree, ItemType& item, bool& found) // Recursively searches tree for item. // Post: If there is an element someItem whose key matches item's, // found is true and item is set to a copy of someItem; // otherwise found is false and item is unchanged. { if (tree == NULL) found = false; // item is not found. else if (item info) Retrieve(tree->left, item, found); // Search left subtree. else if (item > tree->info) Retrieve(tree->right, item, found);// Search right subtree. else { item = tree->info; // item is found. found = true; } }

void Insert(TreeNode*& tree, ItemType item);

void TreeType::PutItem(ItemType item) // Calls recursive function Insert to insert item into tree. { Insert(root, item); }

void Insert(TreeNode*& tree, ItemType item) // Inserts item into tree. // Post: item is in tree; search property is maintained. { if (tree == NULL) {// Insertion place found. tree = new TreeNode; tree->right = NULL; tree->left = NULL; tree->info = item; } else if (item info) Insert(tree->left, item); // Insert in left subtree. else Insert(tree->right, item); // Insert in right subtree. } void DeleteNode(TreeNode*& tree);

void Delete(TreeNode*& tree, ItemType item);

void TreeType::DeleteItem(ItemType item) // Calls recursive function Delete to delete item from tree. { Delete(root, item);

}

void Delete(TreeNode*& tree, ItemType item) // Deletes item from tree. // Post: item is not in tree. { if (item info) Delete(tree->left, item); // Look in left subtree. else if (item > tree->info) Delete(tree->right, item); // Look in right subtree. else DeleteNode(tree); // Node found; call DeleteNode. }

void GetPredecessor(TreeNode* tree, ItemType& data);

void DeleteNode(TreeNode*& tree) // Deletes the node pointed to by tree. // Post: The user's data in the node pointed to by tree is no // longer in the tree. If tree is a leaf node or has only // non-NULL child pointer the node pointed to by tree is // deleted; otherwise, the user's data is replaced by its // logical predecessor and the predecessor's node is deleted. { 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); // Delete predecessor node. } }

void GetPredecessor(TreeNode* tree, ItemType& data) // Sets data to the info member of the right-most node in tree. { while (tree->right != NULL) tree = tree->right; data = tree->info; }

void PrintTree(TreeNode* tree, std::ofstream& outFile) // Prints info member of items in tree in sorted order on outFile. { if (tree != NULL) { PrintTree(tree->left, outFile); // Print left subtree. outFile info; PrintTree(tree->right, outFile); // Print right subtree. } }

void TreeType::Print(std::ofstream& outFile) const // Calls recursive function Print to print items in the tree. { PrintTree(root, outFile); }

void TreeType::Ancestors(ItemType item,std::ofstream& outFile){ //Precondition: Tree is initilaized //PostCondition: The ancestors of the node whose info member is value have been printed TreeNode * temp = new TreeNode; temp = root;

if(root==NULL){ outFile

while(temp->info!=item){ outFile info

if(temp->info right; } else if(temp->info > item){ temp = temp->left;

}//else if

}//while

}//else }//ancestors

bool TreeType::printAncestors(TreeNode *root,ItemType item,std::ofstream& outFile)const { //TreeNode * root = new TreeNode; /* base cases */ if (root == NULL)

return false;

if (root->info == item) return true;

/* If target is present in either left or right subtree of this node, then print this node */ if ( printAncestors(root->left, item,outFile) || printAncestors(root->right, item,outFile) ) { outFile info

/* Else return false */ return false; }

TreeType::TreeType() { root = NULL; }

void Destroy(TreeNode*& tree);

TreeType::~TreeType() // Calls recursive function Destroy to destroy the tree. { Destroy(root); }

void Destroy(TreeNode*& tree) // Post: tree is empty; nodes have been deallocated. { if (tree != NULL) { Destroy(tree->left); Destroy(tree->right); delete tree; } }

void TreeType::MakeEmpty() { Destroy(root); root = NULL; }

void CopyTree(TreeNode*& copy, const TreeNode* originalTree);

TreeType::TreeType(const TreeType& originalTree) // Calls recursive function CopyTree to copy originalTree // into root. { CopyTree(root, originalTree.root); }

void TreeType::operator= (const TreeType& originalTree) // Calls recursive function CopyTree to copy originalTree // into root. { { if (&originalTree == this) return; // Ignore assigning self to self Destroy(root); // Deallocate existing tree nodes CopyTree(root, originalTree.root); }

} void CopyTree(TreeNode*& copy, const TreeNode* originalTree) // Post: copy is the root of a tree that is a duplicate // of originalTree. { if (originalTree == NULL) copy = NULL; else { copy = new TreeNode; copy->info = originalTree->info; CopyTree(copy->left, originalTree->left); CopyTree(copy->right, originalTree->right); } } // Function prototypes for auxiliary functions.

void PreOrder(TreeNode*, QueType&); // Enqueues tree items in preorder.

void InOrder(TreeNode*, QueType&); // Enqueues tree items in inorder.

void PostOrder(TreeNode*, QueType&); // Enqueues tree items in postorder.

void TreeType::ResetTree(OrderType order) // Calls function to create a queue of the tree elements in // the desired order. { switch (order) { case PRE_ORDER : PreOrder(root, preQue); break; case IN_ORDER : InOrder(root, inQue); break; case POST_ORDER: PostOrder(root, postQue); break; } }

void PreOrder(TreeNode* tree, QueType& preQue) // Post: preQue contains the tree items in preorder. { if (tree != NULL) { preQue.Enqueue(tree->info); PreOrder(tree->left, preQue); PreOrder(tree->right, preQue); } }

void InOrder(TreeNode* tree, QueType& inQue) // Post: inQue contains the tree items in inorder. { if (tree != NULL) { InOrder(tree->left, inQue); inQue.Enqueue(tree->info); InOrder(tree->right, inQue); } }

void PostOrder(TreeNode* tree, QueType& postQue) // Post: postQue contains the tree items in postorder. { if (tree != NULL) { PostOrder(tree->left, postQue); PostOrder(tree->right, postQue); postQue.Enqueue(tree->info); } }

ItemType TreeType::GetNextItem(OrderType order, bool& finished) // Returns the next item in the desired order. // Post: For the desired order, item is the next item in the queue. // If item is the last one in the queue, finished is true; // otherwise finished is false. { finished = false; ItemType item; 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; } return item; }

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

35. Write a client function MakeTree that creates a binary search tree from the ele- ments in a sorted list ofintegers. You cannot traverse the list inserting the elements in order, as that would produce a tree that has N levels. You must create a tree with at most log2N 1 levels