Binary Assign

/** * @author Jane Programmer * @cwid 123 45 678 * @class COSC 2336, Spring 2019 * @ide Visual Studio Community 2017 * @date April 8, 2019 * @assg Assignment 12 * * @description Assignment 12 Binary Search Trees */ #include <iostream> #include <string> #include <sstream> #include "BinaryTree.hpp" using namespace std; /** BinaryTree default constructor * Default constructor for a BinaryTree collection. The default * behavior is to create an initially empty tree with no * items currently in the tree. */ BinaryTree::BinaryTree() { root = NULL; nodeCount = 0; } /** BinaryTree destructor * The destructor for a BinaryTree. Be a good manager of memory * and make sure when a BinaryTree goes out of scope we free * up all of its memory being managed. The real work is done * by the clear() member function, whose purpose is exactly this, * to clear all items from the tree and return it back to an * empty state. */ BinaryTree::~BinaryTree() { // uncomment this after you implement clear in step X, to ensure // when trees are destructed that all memory for allocated nodes // is freed up. //clear(); } /** BinaryTree size * Return the current size of this BinaryTree. Here size means the * current number of nodes/items currently being managed by the * BinaryTree. * * @returns int Returns the current size of this BinaryTree. */ int BinaryTree::size() const { return nodeCount; } /** BinaryTree tostring * This is the recursive private function that does the actual * work of creating a string representation of the BinaryTree. * We perform a (recursive) inorder traversal, constructing a * string object, to be returned as a result of this function. * * @param node The BinaryTreeNode we are currently processing. * * @returns string Returns the constructed string of the BinaryTree * contents in ascending sorted order. */ string BinaryTree::tostring(BinaryTreeNode* node) const { // base case, if node is null, just return empty string, which // stops the recursing if (node == NULL) { return ""; } // general case, do an inorder traversal and build tring else { ostringstream out; // do an inorder traversal out << tostring(node->left) << node->item << " " << tostring(node->right); return out.str(); } } /** BinaryTree tostring * Gather the contents and return (for display) as a string. * We use an inorder traversal to get the contents and construct * the string in sorted order. This function depends on operator<< * being defined for the item type being held by the BinaryTreeNode. * This function is actually only the public interface, the * actual work is done by the private recursive tostring() function. * * @returns string Returns the constructed string of the BinaryTree * contents in ascending sorted order. */ string BinaryTree::tostring() const { ostringstream out; out << "size: " << nodeCount << " items: [ " << tostring(root) << "]" << endl; return out.str(); } /** BinaryTree output stream operator * Friend function for BinaryTree, overload output stream * operator to allow easy output of BinaryTree representation * to an output stream. * * @param out The output stream object we are inserting a string/ * representation into. * @param aTree A reference to the actual BinaryTree object to be * displayed on the output stream. * * @returns ostream Returns reference to the output stream after * we insert the BinaryTree contents into it. */ ostream& operator<<(ostream& out, const BinaryTree& aTree) { out << aTree.tostring(); return out; } BinaryTreeNode* BinaryTree::insert(BinaryTreeNode* node, const int item) { // Base Cases: root is null or key is present at root if (root == NULL || root->item == item) return root; // Key is greater than root's key if (root->item < item) return insert(root->right, item); // Key is smaller than root's key return insert(root->left, item); } void BinaryTree::insert(const int item) { BinaryTreeNode* newNode; //Pointer to a new node //Create a new node and store num in it newNode = new BinaryTreeNode; newNode-> item = item; newNode->left = newNode->right = NULL; //Insert the node insert(root, item); }