Assg 12: Binary Search Trees COSC 2336 Spring 2019

profileunique12
Assg12.zip
Home>Computer Science homework help>Assg 12: Binary Search Trees COSC 2336 Spring 2019

Assg12/assg-12.cpp

Assg12/assg-12.cpp

/** 
 *  @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   < cassert >
#include   < iostream >
#include   "BinaryTree.hpp"

using   namespace  std ;


/** main 
 * The main entry point for this program.  Execution of this program
 * will begin with this main function.
 *
 *  @param  argc The command line argument count which is the number of
 *     command line arguments provided by user when they started
 *     the program.
 *  @param  argv The command line arguments, an array of character
 *     arrays.
 *
 *  @returns  An int value indicating program exit status.  Usually 0
 *     is returned to indicate normal exit and a non-zero value
 *     is returned to indicate an error condition.
 */
int  main ( int  argc ,   char **  argv )
{
   // -----------------------------------------------------------------------
  cout  <<   "--------------- testing  BinaryTree construction ----------------"   <<  endl ;
   BinaryTree  t ;

  cout  <<   "<constructor> Size of new empty tree: "   <<  t . size ()   <<  endl ;
  cout  <<  t  <<  endl ;
  assert ( t . size ()   ==   0 );
  cout  <<  endl ;

  
   // -----------------------------------------------------------------------
  cout  <<   "--------------- testing  BinaryTree insertion -------------------"   <<  endl ;

   //t.insert(10);
   //cout << "<insert> Inserted into empty tree, size: " << t.size() << endl;
   //cout << t << endl;
   //assert(t.size() == 1);

   //t.insert(3);
   //t.insert(7);
   //t.insert(12);
   //t.insert(15);
   //t.insert(2);

   //cout << "<insert> inserted 5 more items, size: " << t.size() << endl;
   //cout << t << endl;
   //assert(t.size() == 6);
  cout  <<  endl ;

  
   // -----------------------------------------------------------------------
  cout  <<   "--------------- testing  BinaryTree height -------------------"   <<  endl ;
   //cout << "<height> Current tree height: " << t.height() << endl;
   //assert(t.height() == 3);

   // increase height by 2
   //t.insert(4);
   //t.insert(5);
   //cout << "<height> after inserting nodes, height: " << t.height()
   //     << " size: " << t.size() << endl;
   //cout << t << endl;
   //assert(t.height() == 5);
   //assert(t.size() == 8);
  cout  <<  endl ;

  
   // -----------------------------------------------------------------------
  cout  <<   "--------------- testing  BinaryTree clear -------------------"   <<  endl ;
   //t.clear();
   //cout << "<clear> after clearing tree, height: " << t.height()
   //     << " size: " << t.size() << endl;
   //cout << t << endl;
   //assert(t.size() == 0);
   //assert(t.height() == 0);
  cout  <<  endl ;

  
   // return 0 to indicate successful completion
   return   0 ;
}

Assg12/BinaryTree.cpp

Assg12/BinaryTree.cpp

/** 
 *  @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 ;
}

Assg12/BinaryTree.hpp

/** * @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 <string> using namespace std; /** Binary Tree Node * A binary tree node, based on Shaffer binary tree node ADT, pg. 156., * implementation pg. 161. The node class is not the tree. A binary * search tree consists of a structure/colleciton of binary tree nodes, * arranged of course as a binary tree. A binary tree nodes purpose is to * store the key/value of a single item being managed, and to keep links * to left and right children. * * We assume both key and value are the same single item here. This * version is not templatized, we create nodes that hold simple int * values, but we could parameritize this to hold arbitrary value * types. * * @value item The item held by this binary tree node. This item is * both the key and the value of the item being stored. In * alternative implementations we might want to split the key and * value into two separate fields. * @value left, right Pointers to the left child and right child nodes * of this node. These can be null to indicate that not left/right * child exists. If both are null, then this node is a leaf node. */ struct BinaryTreeNode { int item; BinaryTreeNode* left; BinaryTreeNode* right; }; /** Binary Tree * A binary search tree implementation, using pointers/linked list, based * on Shaffer example implementation pg. 171. This is the class that * actually manages/implements the tree. It contains a single * pointer to the root node at the top (or bottom depending on how you * view it) of the tree. We also maintain a count of the number of nodes * currently in the tree. This class will support insertion * and searching for new nodes. * * @value root A pointer to the root node at the top of the * tree. When the tree is initially created and/or when the tree is * empty then root will be null. * @value nodeCount The count of the number of nodes/items currently in * this binary tree. */ class BinaryTree { private: BinaryTreeNode* root; int nodeCount; // private helper methods, do actual work usually using recursion string tostring(BinaryTreeNode* node) const; public: // constructors and destructors BinaryTree(); ~BinaryTree(); // accessor methods int size() const; // insertion, deletion and searching // tree traversal and display string tostring() const; friend ostream& operator<<(ostream& out, const BinaryTree& aTree); };