Data structure and alogorithm

/** @file BinaryTree.cpp * @brief Implementation file with class member function implementations for * the BinaryTree class for Assignment 11 binary trees * * @author Jane Programmer * @note cwid : 123 45 678 * @note class: COSC 2336, Summer 2020 * @note ide : Atom Text Editor 1.46.0 / build package / GNU gcc tools * @note assg : Assignment 11 * @date June 1, 2020 * * Assignment 11 BinaryTrees. Implement some missing member functions for a * BinaryTree ADT data structure. This header file contains the declaration of * the BinaryTree This implementation file contains the implementations of the * BinaryTree ADT data structure. You need to add the implementations for the * member functions for this assignment to this file. */ #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; }