Binary Search Trees COSC 2336
Assg 12 Binary Search Trees COSC 2336/assg-12.cpp
Assg 12 Binary Search Trees COSC 2336/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 << " 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 << " 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 << " inserted 5 more items, size: ” << t.size() << endl; //cout << t << endl; //assert(t.size() == 6); cout << endl ; // ----------------------------------------------------------------------- cout << "--------------- testing BinaryTree height -------------------" << endl ; //cout << " Current tree height: ” << t.height() << endl; //assert(t.height() == 3); // increase height by 2 //t.insert(4); //t.insert(5); //cout << " 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 << " 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 ; } Assg 12 Binary Search Trees COSC 2336/assg-12.pdf Assg 12: Binary Search Trees COSC 2336 Spring 2019 April 10, 2019 Dates: Due: Sunday April 21, by Midnight Objectives ? Practice recursive algorithms ? Learn how to construct a binary tree using pointers/linked nodes ? Learn about binary tree traversal Description In this assignment you will be given the beginning of a BinaryTree imple- mentation using linked nodes via pointers. You will be implementing some of the basic function of a BinaryTree abstract data type. The abstraction we are using for the BinaryTreeNode and the BinaryTree are similar to the Sha?er BSTNode (pg. 156,161) and the BST abstract class and linked pointer implementation (Sha?er pg. 171), but we will de?ne our own version and simplify some of the functions and interface. You have been given a BinaryTree.[cpp|hpp] ?le that de?nes the BinaryTreeNode structure and BinaryTree class. This class is current not templatized, the constructed trees only hold items of simple type int (one of the extra credit opportunities suggests you templatize your resulting class). The BinaryTree has a constructor, and you have been provided a tostring() method and an overloaded operator?() so that you can display the current contents of the tree. For this assignment you need to perform the following tasks. 1 1. In order to test your class, we ?rst have to get a working capability to insert new items into the BinaryTree, which isn't the simplest task to start with, but we can't really test others until we can add new items. For many of the functions in this assignment, you will be required to implement them using a recursive function. Thus many of the func- tions for your BinaryTree will have a public function that asks as the interface that is called by users of the BinaryTree, and a private ver- sion that actually does the work using a recursive algorithm. I will give you the signature you need for the insert() functions: class BinaryTree { private: BinaryTreeNode* insert(BinaryTreeNode* node, const int item); public: void insert(const int item); } Lets start ?rt with the public insert() function. This function is the public interface to insert a new item into the tree. Since we are only implementing a tree of int items, you simply pass in the int value that is to be inserted. This function basically only needs to call the private insert() function, passing in the current root of the tree as the ?rst parameter, and the item to be inserted as the second parameter. Notice that the private insert() returns a pointer to a BinaryTreeNode. The private insert() function is a recursive function. The base case is simple. If the node you pass in is NULL, then that means you have found the location where a new node should be created and inserted. So for the base case, when node is NULL you should dynamically create a new BinaryTreeNode item, assign the item and make sure that the left and right pointers are initialized to NULL. When you create a new node like this, you should return the newly created BinaryTreeNode as a result from the insert() function (notice that the private insert() should always return a BinaryTreeNode*). This is because, when a new node is allocated, it gets returned and it needs to be assigned to something so it gets inserted into the tree. For example, think of what happens initially when the BinaryTree is empty. In that case the root of the tree will be NULL. When you call the recursive insert() on the initially empty tree, you need to assign the returned value back into 2 root in the non-recursive function (and you also need to increment the nodeCount by 1 in your public non-recursive function). The general cases for the recursion are as follows. Since we are imple- menting a binary search tree, we need to keep the tree organized/sorted. Thus in the general case, remember that we have already tested that the node is not NULL, thus there is an item in the node->item. So for the general case, if the item we are inserting is less than or equal to node->item, then we need to insert it into the left child subtree (it is important to use <= comparison to determine if to go left here). To do this you will basically just call insert() recursively with the item to be inserted, and passing in node->left as the ?rst parameter. Of course, in the case that the item is greater than the one in the cur- rent node, you instead need to call insert() on the node->right child subtree.

And ?nally, make sure you take care of correctly returning a result from the recursive insert(). Here when you call insert() on ei- ther the left or right child subtree, the function should return a BinaryTreeNode*. For example, imagine that you are inserting into the left child, and there is no left subtree, and thus left will be NULL. In that case the recursive call to insert() will create a new node dynamically and return it. So the return value from calling insert() needs to be assiged back into something. If you are calling insert() on the left child, the returned result should be assigned back into node->left, and if you are calling on the right child, the returned re- sult should be assigned back into node->right. Again this is because when we ?nally ?nd where the node needs to be linked into the tree, we will do it at either an empty left or right subtree child. Thus in order to link the newly created node into the tree, we need to as- sign the returned pointer back into either node->left or node->right appropriately. And ?nally, after you call insert() recursively in the general case, you do have to remember that you always have to return a BinaryTreeNode*. For the base case, when you dynamically create a new node, the new node is what you return. But in the general case, you should simply return the current node. This will get (re)assigned when you return back to the parent, but this is ?ne and expected.

To summarize, you need to do the following to implement the insert() functionality:

? The public insert() should simply call the private insert() on

3

the root node.

? In the public insert() the return result should be assigned back into root.

? The public insert() is also responsible for incrementing the nodeCount member variable.

? For the private recursive insert() the base case occurs when a NULL node is received, in which case a new BinaryTreeNode is dynamically created and returned.

? For the general case, if node is not NULL, then you instead either need to call insert() recursively on the left or right subchild, depending on if the item to be inserted is <= or > the node->item respectively.

? Don’t forget in the general case, that the returned result from calling insert() needs to be assigned back into left or right as appropriate.

? And ?nally, the recursive insert() always returns a value, and in the general case you should simply just return the node as the result.

2. Next we have a relatively easier set of tasks to accomplish. Once you have insert() working and tested, we will implement a function to determine the current height() of the tree. You should read our textbook to make sure you know the de?nition of the height of a tree.

height() needs 2 functions again, a public function which is the in- terface, and a private function that is recursive and does the actual work. Both the public and private height() functions should be de- clared as const functions, as they do not actually modify the contents of the tree. Both functions return an int result. The public function doesn’t have any input parameters, but the private function should take a single BinaryTreeNode* as its input parameter.

The public height() function should be very simply, it should simply call the private height() on the root node of the binary tree, and return the resulting calculated height.

For the private height() function, the base case is that if node is NULL then the height is 0, so you should return 0 in that case. Otherwise, in the general case, the height is conceptuall 1 plus the height of the bigger of the heights of the two subtree children left and right. Thus

4

to calculate the height for a given node, recursive calculate height on both the left and right children, ?nd the maximum of these two, add 1 to it, and that is the height of the node.

3. The third and ?nal task is to implement the clear() abstract function. The clear() function basically clears out all of the stored items from the tree, deallocating and returning the memory used for the node storage back to the OS.

As with all of the functions for this assignment, clear() needs both a public function that acts as the interface, and a private recursive version that does all of the work. The implementation of the pub- lic clear() is almost as simple as the previous height() function. The public clear() should simply call the private clear(), passing in the current root of the tree. Both the public and private versions of clear() should be void functions, they do not return any result or value.

The private recursive clear() is a void function, as we mentioned, and it takes a single BinaryTreeNode* parameter as its input. This function is also relatively rather easy. The base case is that, if node is NULL then you don’t have to do anything, simply return, as you have reached the end of the recursion in that case. For the general case, all you need to do is simply call clear() recursively on the left and right subtree children ?rst. Then after this you can safely call delete on the node, because all of the nodes in the two subtree children will have been deleted by the recursion, and now you can safely delete and free up the memory for the node.

In this assignment you will only be given 3 ?les in total. The “assg- 12.cpp” ?le contains tests of the BinaryTree insert(), height() and clear() functions you are to implement. You will also be given “BinaryTree.hpp” which is a header ?le containing the de?nition of the BinaryTreeNode struc- ture and BinaryTree class, including initial implementations for constructors and for displaying the tree as a string.

Here is an example of the output you should get if your code is passing all of the tests and is able to run the simulation. You may not get the exact same statistics for the runSimulation() output, as the simulation is generating random numbers, but you should see similar values.

————— testing BinaryTree construction —————-

Size of new empty tree: 0

5

size: 0 items: [ ]

————— testing BinaryTree insertion ——————-

Inserted into empty tree, size: 1

size: 1 items: [ 10 ]

inserted 5 more items, size: 6

size: 6 items: [ 2 3 7 10 12 15 ]

————— testing BinaryTree height ——————-

Current tree height: 3

after inserting nodes, height: 5 size: 8

size: 8 items: [ 2 3 4 5 7 10 12 15 ]

————— testing BinaryTree clear ——————-

after clearing tree, height: 0 size: 0

size: 0 items: [ ]

Assignment Submission

A MyLeoOnline submission folder has been created for this assignment. You should attach and upload your completed “BinaryTree.[hpp|cpp]” source ?les to the submission folder to complete this assignment. You do not need to submit your “assg-12.cpp” ?le with test. But please only submit the asked for source code ?les, I do not need your build projects, executables, project ?les, etc.

Requirements and Grading Rubrics

Program Execution, Output and Functional Requirements

1. Your program must compile, run and produce some sort of output to be graded. 0 if not satis?ed.

2. (40 pts.) insert() functionality is implemented correctly. Base and general cases are written as described. Functions work for trees with items and when tree is empty.

6

3. (30 pts.) height() functionality is implemented correctly. Correctly implement stated base and general cases using recursion.

4. (30 pts.) clear() functionality is implemented correctly. Correctly implement stated base and general cases using recursion.

5. (5 pts. extra credit) Of course it is not really useful to have a BinaryTree container that can only handle int types. Templatize your working class so it works as a container for any type of object. If you do this, please make a new version of “assg-12.cpp” that works for your tem- platized version, passes all of the tests for an container, and add tests for a di?erent type, like .

6. (5 pts. extra credit) Implement a printTree() method. The tostring() method I gave you doesn’t really show the structure of the tree. Of course if you had a graphical environment you could draw a picture of the tree. But if you only have a terminal for output, you can display the tree as a tree on its side relatively easy. To do this, you need again both a public and private printTree() method. The private method is the recursive implementation, and as usual it takes a BinaryTreeNode* as a parameter, and a second parameter indicate the o?set or height of this node in the tree. If you perform a reverse preorder traversal of the tree, spacing or tabbing over according to the tree height, then you can display the approximate structure of the tree on the terminal. Recall that preorder traversal is performed by visiting left, then ourself, then our right child. So a reverse preorder is performed by ?rst visiting our right, then ourself, then our left child.

7. (10 pts. extra credit) The BinaryTree is missing a big piece of fun- cionality, the ability to remove items that are in the tree. You can read our textbook for a description of how you can implement functions to remove items from the tree. It is a good exercise, and quite a bit more challenging than the insert(). The simplest case is if you want to remove a node that is a leaf node (both left and right are NULL, indicating no child subtrees). When removing a leaf, you can simply delete the node and set the parent pointer in the tree to this node to NULL. When the node only has 1 subtree, either the left or the right, you can also still do something relatively simple to assign the orphaned subtree back to the parent, then delete the node with the item that is to be removed. But when the node to be deleted also has both left and right child subtrees, then you need to do some rearrangements

7

of the tree. The Sha?er textbook discusses how to implement removal from a binary tree as an example you can follow.

Program Style

Your programs must conform to the style and formatting guidelines given for this class. The following is a list of the guidelines that are required for the assignment to be submitted this week.

1. Most importantly, make sure you ?gure out how to set your indentation settings correctly. All programs must use 2 spaces for all indentation levels, and all indentation levels must be correctly indented. Also all tabs must be removed from ?les, and only 2 spaces used for indentation.

2. A function header must be present for member functions you de?ne. You must give a short description of the function, and document all of the input parameters to the function, as well as the return value and data type of the function if it returns a value for the member functions, just like for regular functions. However, setter and getter methods do not require function headers.

3. You should have a document header for your class. The class header document should give a description of the class. Also you should doc- ument all private member variables that the class manages in the class document header.

4. Do not include any statements (such as system(“pause”) or inputting a key from the user to continue) that are meant to keep the terminal from going away. Do not include any code that is speci?c to a single operating system, such as the system(“pause”) which is Microsoft Windows speci?c.

8

Assg 12 Binary Search Trees COSC 2336/BinaryTree.cpp
Assg 12 Binary Search Trees COSC 2336/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 , Read more Applied Sciences Architecture and Design Biology Business & Finance Chemistry Computer Science Geography Geology Education Engineering English Environmental science Spanish Government History Human Resource Management Information Systems Law Literature Mathematics Nursing Physics Political Science Psychology Reading Science Social Science Home Homework Answers Blog Archive Tags Reviews Contact twitterfacebook Copyright © 2022 SweetStudy.com