#include "ITreeType.h" 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 < tree->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 FindNode(TreeNode* tree, ItemType item, TreeNode*& nodePtr, TreeNode*& parentPtr) // Post: If a node is found with the same key as itemπs, then // nodePtr points to that node and parentPtr points to its // parent node. If the root node has the same key as itemπs, // parentPtr is NULL. If no node has the same key, then // nodePtr is NULL and parentPtr points to the node in the // tree that is the logical parent of item. { nodePtr = tree; parentPtr = NULL; bool found = false; while (nodePtr != NULL && !found) { if (item < nodePtr->info) { parentPtr = nodePtr; nodePtr = nodePtr->left; } else if (item > nodePtr->info) { parentPtr = nodePtr; nodePtr = nodePtr->right; } else found = true; } } void GetPredecessor(TreeNode* tree, ItemType& data); void Delete(TreeNode*& tree, ItemType item); 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); } } void Delete(TreeNode*& tree, ItemType item) // Deletes item from tree. // Post: item is not in tree. { if (item < tree->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) // Sets data to the info member of the right-most node in tree. { while (tree->right != NULL) tree = tree->right; data = tree->info; } void TreeType::PutItem(ItemType item) // Post: item is in tree. { TreeNode* newNode; TreeNode* nodePtr; TreeNode* parentPtr; newNode = new TreeNode; newNode->info = item; newNode->left = NULL; newNode->right = NULL; FindNode(root, item, nodePtr, parentPtr); if (parentPtr == NULL) // Insert as root. root = newNode; else if (item < parentPtr->info) parentPtr->left = newNode; else parentPtr->right = newNode; } void TreeType::DeleteItem(ItemType item) // Post: There is no node in the tree whose info member // matches item. { TreeNode* nodePtr; TreeNode* parentPtr; FindNode(root, item, nodePtr, parentPtr); if (nodePtr == root) DeleteNode(root); else if (parentPtr->left == nodePtr) DeleteNode(parentPtr->left); else DeleteNode(parentPtr->right); } 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 << tree->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); } 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; }