Write IN c++ ONLY

BSTree.cpp

/// \mainpage BSTree.cpp /// \version 1 /// \date 08/04/2017 /// \authors Jannath Khan, Joe Latessa

#include "BSTree.h"

/// Anonymous Inner Class Constructor /// Class objects of BSTree are instantiated with the BSTree class's insert() /// method. Objects of this type make up the binary search tree's nodes. /// Precondition: dataItem is UNINITIALIZED /// left is UNINITIALIZED /// right is UNINITIALIZED /// Postcondition: dataItem = nodeDataItem /// left = leftPtr /// right = rightPtr template BSTree::BSTreeNode::BSTreeNode(const DataType& nodeDataItem, BSTreeNode* leftPtr, BSTreeNode* rightPtr) { dataItem = nodeDataItem; left = leftPtr; right = rightPtr; }

/// Constructor /// This operation instantiates an empty tree in which each insert is a /// dynamically allocated node. /// Precondition: pointer to the root node is UNINITIALIZED /// Postcondition: root = NULL; template BSTree::BSTree() { root = NULL; }

/// Copy constructor /// This operation instantiates an empty binary search tree with the root /// pointer set to NULL. If the source object's tree contains nodes, the /// copyHelper method is called to deep copy the source object nodes /// to this object. /// Precondition: pointer to the rood node is UNINITIALIZED /// Postcondition: root = other.root /// this object's child nodes = other object's child nodes template BSTree::BSTree(const BSTree& other) { try { root = NULL; if (other.root != NULL) copyHelper(this->root, other.root); } catch (...) { cout

/// Method to overload operator= /// This operation calls deleteHeapHelper() to delete this object's /// currently allocated nodes (if they exist). If the source object /// referenced in the parameter is NULL, this object remains empty. If /// the source object's tree contains nodes, the copyHelper method is /// called to deep copy the source object nodes to this object. /// Precondition: root points to NULL or previously allocated nodes. /// Postcondition: this object's previously allocated nodes (if any) are /// deleted. /// if source object has nodes, source nodes are deep /// copied. A reference to this object is returned. template BSTree& BSTree::operator=(const BSTree& other) { if (this != &other) { try { deleteHelper(root); if (other->root != NULL) copyHelper(this->root, other->root); } catch (...) { cout

/// Destructor /// This operation calls deleteHelper() to delete the tree's nodes /// (if they exist), and set the root pointer to NULL. /// Precondition: root points to previously allocated nodes. /// Postcondition: previously allocated nodes (if any) are deleted. /// root = NULL template BSTree::~BSTree() { clear(); }

/// Insert Method /// This operation calls the retrieve method to check whether the newDataItem /// to be inserted is a duplicate. If it is a duplicate, no new item is /// inserted. If newDataItem is not already found in the tree, the /// insertHelper method is called to insert newDataItem based upon its key. /// Precondition: newDataItem is not yet inserted in the tree. /// Postcondition: newDataItem is inserted in the tree based upon its key. template void BSTree::insert(const DataType& newDataItem) { try { DataType duplicateHolder; KeyType key = newDataItem.getKey();

if (retrieve(key, duplicateHolder)) return;

insertHelper(root, newDataItem, key); } catch (...) { cout

/// Retrieve Method /// This operation calls the retrieveHelper method to search the tree for /// a dataItem based on its key: searchKey. If the dataItme is found, /// retrieveHelper assigns the dataItem to the searchDataItem reference /// parameter. True is returned if the dataItem is found. Else false. /// Precondition: searchDataItem is unassigned. /// Postcondition: if found, searchDataItem = the dataItem of the found item. /// true is returned. Else, false is returned. template bool BSTree::retrieve(const KeyType& searchKey, DataType& searchDataItem) const { return retrieveHelper(searchKey, root, searchDataItem); }

/// Remove Method /// This operation checks whether the tree is empty. If the tree is not /// empty, the removeHelper method is called to search the tree for /// the dataItem based upon its key: deleteKey. If the dataItem is found, /// removeHelper removes the specified node and restructures the binary tree. /// True is returned if the dataItem is found. Else false. /// Precondition: a dataItem to be searched might be in the tree /// Postcondition: if found, the node is removed and the tree is /// restructured. /// if found, true is returned. Else, false is returned. template bool BSTree::remove(const KeyType& deleteKey) { if (root != NULL) return removeHelper(deleteKey, root);

return false; }

/// Write Keys Method /// This operation checks whether the tree is empty. If it is not empty, /// writeKeysHelper is called to recursively traverse the tree and output /// the key values in ascending order. /// Precondition: root points to the trees root node /// Postcondition: the tree has been traversed and key values are output in /// ascending order. template void BSTree::writeKeys() const { if (root != NULL) writeKeysHelper(root); cout

/// Clear Method /// This operation checks whether the tree is empty. If it is not empty, /// the deleteHelper method is called to delete the tree's nodes /// and set the root pointer to NULL. /// Precondition: root points to previously allocated nodes. /// Postcondition: previously allocated nodes (if any) are deleted. /// root = NULL template void BSTree::clear() { if (root != NULL) { deleteHelper(root); root = NULL; } }

/// isEmpty Method /// This operation checks whether the binary search tree is empty. /// Postcondition: returns true if root == NULL. Else false. template bool BSTree::isEmpty() const { return root == NULL; }

/// Show Structure Method /// Outputs the keys in a binary search tree. The tree is output /// rotated counterclockwise 90 degrees from its conventional /// orientation using a "reverse" inorder traversal. This operation is /// intended for testing and debugging purposes only. /// Postcondition: A visual representation of the tree structure is /// output to screen. template void BSTree::showStructure() const { if (root == 0) cout

/// Show Helper Method /// Recursive helper for showStructure. /// Outputs the subtree whose root node is pointed to by p. /// Parameter level is the level of this node within the tree. /// Postcondition: A visual representation of the tree structure is /// output to screen. template void BSTree::showHelper(BSTreeNode *p, int level) const { int j; // Loop counter

if (p != 0) { showHelper(p->right, level + 1); // Output right subtree for (j = 0; j dataItem.getKey(); // Output key if ((p->left != 0) && // Output "connector" (p->right != 0)) cout right != 0) cout left != 0) cout left, level + 1); // Output left subtree } }

/// Copy Helper Method /// Recursive helper for copy constructor and operator= overload. /// This operation instantiates a BSTreeNode object with source node's /// dataItem, left pointer, and right pointer as data members. If the left /// pointer is not NULL, copyHelper is recursively called using this node's /// and the source node's left pointers as arguments. If the right /// pointer is not NULL, copyHelper is recursively called using this node's /// and the source node's right pointers as arguments.assigned /// Precondition: root pointer (passed in as ptr) = NULL /// Postcondition: root = other.root /// this object's child nodes = other object's child nodes template void BSTree::copyHelper(BSTreeNode*& ptr, BSTreeNode* sourceNode) { ptr = new BSTreeNode(sourceNode->dataItem, sourceNode->left, sourceNode->right);

if (ptr->left != NULL) copyHelper(ptr->left, sourceNode->left);

if (ptr->right != NULL) copyHelper(ptr->right, sourceNode->right); }

/// Delete Helper Method /// Recursive helper to delete all binary tree nodes. /// If the pointer to the left node is not NULL, deleteHelper is recursively /// called sending in the pointer to the left node as an argument. If the /// pointer to the right node is not NULL, deleteHelper is recursively /// called sending in the pointer to the right node as an argument. When a /// node with no child nodes is reached, that node is deleted. /// Precondition: root (passed in as ptr) is not NULL. /// Postcondition: the tree's nodes are deleted. root = NULL. template void BSTree::deleteHelper(BSTreeNode*& ptr) { if (ptr->left != NULL) deleteHelper(ptr->left);

if (ptr->right != NULL) deleteHelper(ptr->right);

delete ptr; }

/// Insert Helper Method /// Recursive helper to insert a node in its proper tree position. /// If the node type pointer passed in the argument is NULL, a BSTreeNode /// object is instantiated where ptr points. the newDataItem parameter is /// assigned to ptr->dataItem. ptr->left and ptr->right are NULL. If the /// node type pointer passed in the argument is not NULL, the node's dataItem /// key is compared to the parameter newDataItem's key. If newDataItem's key /// value is less than ptr->dataItem's key value, insertHelper is recursively /// called on ptr->left. If newDataItem's key value is more than /// ptr->dataItem's key value, insertHelper is recursively called on /// ptr->right. /// Note: insertHelper will not be called if the newDataItem's /// key == ptr->dataItem's key. The check for duplicate keys /// is handled in the insert method. /// Precondition: root (passed in as ptr) is not NULL. ptr->dataItem's key /// and newDataItem's key are not duplicates. /// Postcondition: a new binary tree node is instantiated and inserted /// according to newDataItem's key value. /// ptr->dataItem = newDataItem /// ptr->left = NULL /// ptr->right = NULL template void BSTree::insertHelper(BSTreeNode*& ptr, const DataType& newDataItem, KeyType& key) { if (ptr == NULL) // insert ptr = new BSTreeNode(newDataItem, NULL, NULL); else if (newDataItem.getKey() dataItem.getKey()) insertHelper(ptr->left, newDataItem, key); // search left else insertHelper(ptr->right, newDataItem, key); // search right }

/// Retrieve Helper Method /// Recursive helper to search binary tree for a given key value. /// This operation checks whether a given searchKey value matches /// the dataItem key value of the node pointed to by the parameter /// treePosition. If a match is found, the found dataItem is assigned /// to the reference parameter searchDataItem and true is returned. /// If searchKey is less than the value of the current dataItem's key, /// retrieveHelper is called on the current node's left pointer. If /// searchKey is greater than the value of the current dataItem's key, /// retrieveHelper is called on the current node's right pointer. /// Precondition: treePosition initially points to the BSTree's root node. /// Postcondition: if found, searchDataItem = the dataItem of the found item. /// true is returned. Else, false is returned. template bool BSTree::retrieveHelper(const KeyType& searchKey, BSTreeNode* treePosition, DataType& searchDataItem) const { bool found = false;

if (treePosition == NULL) return found;

if (searchKey == treePosition->dataItem.getKey()) { searchDataItem = treePosition->dataItem; found = true; return found; } else if (searchKey dataItem.getKey()) found = retrieveHelper(searchKey, treePosition->left, searchDataItem); else found = retrieveHelper(searchKey, treePosition->right, searchDataItem); }

/// Write Keys Helper Method /// Recursive helper to output keys in ascending order. /// writeKeysHelper is called recursively on the left nodes /// until a node with no left (smaller) child is reached. That key value /// is then output. writeKeysHelper is called on a right node (which will /// begin the recursive process of checking whether that right node has /// its own left children. /// Precondition: root is not NULL /// Postcondition: the tree's dataItem key values are output in ascending /// order. template void BSTree::writeKeysHelper(BSTreeNode* traverse) const { if (traverse != NULL) { writeKeysHelper(traverse->left); if (traverse != NULL) cout dataItem.getKey() right); } }

/// Remove Helper Method /// Recursive helper to remove a specified node from the tree (if it exists) /// and restructure the tree accordingly. This operation first checks /// whether traverse == NULL. /// /// if traverse is NULL, this indicates that the tree is either /// empty or through recursive removeHelper calls, traverse has reached a /// branch's bottom level without finding the searched for deleteKey. /// False is returned. /// /// if the current node (traverse) is not NULL and deleteKey is less than /// the dataItem's key, removeHelper is called on the current node's left /// child. /// /// else if the current node (traverse) is not NULL and deleteKey is greater /// than the dataItem's key, removeHelper is called on the current node's /// right child. /// /// else if current node is not NULL and its left and right children are also /// not NULL (meaning the current node has two children), and the keys match, /// smallestOnRight = the smallest key value along the path of the current /// node's right child. This dataItem with the smallest key value along the /// path of the current node's right child is assigned as the dataItem of the /// node with the original key value to be removed. removeHelper is then /// called on the current node's right child to remove the node whose /// dataItem was just copied to the current node. /// /// else the keys match, and the current node has 1 or 0 children. A /// temporary pointer toBeRemoved points to the node to be removed and the /// current node traverse then points to whichever of the current node's /// children is not NULL. If both children are NULL, assigning traverse = /// traverse->right effectively means traverse = NULL, and the node traverse /// pointed to before being assigned NULL is deleted. True is returned. /// /// Precondition: root is not NULL. deleteKey is passed in the argument /// and the initial parameter traverse = root. /// Postcondition: if found, the node is removed and the tree is /// restructured. if found, true is returned. /// Else, false is returned. template bool BSTree::removeHelper(const KeyType& deleteKey, BSTreeNode*& traverse) { if (traverse == NULL) /// not found along current branch return false;

// traverse left if key dataItem.getKey()) removeHelper(deleteKey, traverse->left);

// traverse right if key > node's value else if (deleteKey > traverse->dataItem.getKey()) removeHelper(deleteKey, traverse->right);

// has left & right children else if (traverse->left != NULL && traverse->right != NULL) { BSTreeNode* smallestOnRight = traverse->right;

while (smallestOnRight->left != NULL) smallestOnRight = smallestOnRight->left;

traverse->dataItem = smallestOnRight->dataItem;

removeHelper(smallestOnRight->dataItem.getKey(), traverse->right); }

// has one child (left or right) else { BSTreeNode* toBeRemoved = traverse; traverse = (traverse->left != NULL) ? traverse->left : traverse->right; delete toBeRemoved; return true; } }

24 Laboratory Operations ini size trable HashTable int Rogal None the empry hash table. Constructor creates (const HashTables other hlashTable Requirements: Results the hash table to be equivalent to the HashTable copy constructor. Initializes neter HashTables operator" const HashTable& other Requirements: None overloaded assignment operat sets the hash table to be equivalent to the other HashTable object parameter and retums a reference to this object. Hash Table Requirements: None Results: memory used to store a hash table. Destructor. Deallocates (frees the void insert const DataType& newData Item Requirements Results Inserts bei tatalten into the appropriate binary search tree. If a data item with the same key as newDataltem already exists in the binary search tree, then updates dat item with nevDataltem. otherwise, it inserts it in the binary search tree. bool remove const KeyType6 deletekey None Results Searches the hash table for the data item with item s found, then the data the key deleteKey If the data item and returns true. otherwise, returns false bool Require Result fou Req 24 Laboratory Operations ini size trable HashTable int Rogal None the empry hash table. Constructor creates (const HashTables other hlashTable Requirements: Results the hash table to be equivalent to the HashTable copy constructor. Initializes neter HashTables operator" const HashTable& other Requirements: None overloaded assignment operat sets the hash table to be equivalent to the other HashTable object parameter and retums a reference to this object. Hash Table Requirements: None Results: memory used to store a hash table. Destructor. Deallocates (frees the void insert const DataType& newData Item Requirements Results Inserts bei tatalten into the appropriate binary search tree. If a data item with the same key as newDataltem already exists in the binary search tree, then updates dat item with nevDataltem. otherwise, it inserts it in the binary search tree. bool remove const KeyType6 deletekey None Results Searches the hash table for the data item with item s found, then the data the key deleteKey If the data item and returns true. otherwise, returns false bool Require Result fou Re