ASS12/assg-12.cpp

#include

#include

#include"BinaryTree.hpp"

usingnamespacestd;

/..;@paramargcThecommandlineargumentcountwhichisthenumberof

*commandlineargumentsprovidedbyuserwhentheystarted

*theprogram.

*@p..;@returnsAnintvalueindicatingprogramexitstatus.Usually0

*isreturnedtoindicatenormalexitandanon-zerovalue

*isreturnedtoindicateanerrorcondition.

*/

intmain(intargc,char**argv)

{

//-----------------------------------------------------------------------

cout<<"---------------testingBinaryTreeconstruction----------------"<

BinaryTreet;

cout<<"Sizeofnewemptytree:"<

cout<

assert(t.size()==0);

cout<

//-----------------------------------------------------------------------

cout<<"---------------testingBinaryTreeinsertion-------------------"<

//t.insert(10);

//cout<<"Insertedintoemptytree,size:"<

//cout<

//assert(t.size()==1);

//t.insert(3);

//t.insert(7);

//t.insert(12);

//t.insert(15);

//t.insert(2);

//cout<<"inserted5moreitems,size:"<

//cout<

//assert(t.size()==6);

cout<

//-----------------------------------------------------------------------

cout<<"---------------testingBinaryTreeheight-------------------"<

//cout<<"Currenttreeheight:"<

//assert(t.height()==3);

//increaseheightby2

//t.insert(4);

//t.insert(5);

//cout<<"afterinsertingnodes,height:"<

//<<"size:"<

//cout<

//assert(t.height()==5);

//assert(t.size()==8);

cout<

//-----------------------------------------------------------------------

cout<<"---------------testingBinaryTreeclear-------------------"<

//t.clear();

//cout<<"afterclearingtree,height:"<

//<<"size:"<

//cout<

//assert(t.size()==0);

//assert(t.height()==0);

cout<

//return0toindicatesuccessfulcompletion

return0;

}

ASS12/assg-12.pdf

Description

You have been given a BinaryTree.[cpp|hpp] le that denes 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. 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 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 implementing 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 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 denition 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 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 denition 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

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

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

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.

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 dierent 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 oset 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 of the tree. The Shaer textbook discusses how to implement removal from a binary tree as an example you can follow.

ASS12/BinaryTree.cpp

#include

#include

#include

#include"BinaryTree.hpp"

usingnamespacestd;

/**BinaryTreedefaultconstructor

*DefaultconstructorforaBinaryTreecollection.Thedefault

*behavioristocreateaninitiallyemptytreewithno

*itemscurrentlyinthetree.

*/

BinaryTree::BinaryTree()

{

root=NULL;

nodeCount=0;

}

/**BinaryTreedestructor

*ThedestructorforaBinaryTree.Beagoodmanagerofmemory

*andmakesurewhenaBinaryTreegoesoutofscopewefree

*upallofitsmemorybeingmanaged.Therealworkisdone

*bytheclear()memberfunction,whosepurposeisexactlythis,

*toclearallitemsfromthetreeandreturnitbacktoan

*emptystate.

*/

BinaryTree::~BinaryTree()

{

//uncommentthisafteryouimplementclearinstepX,toensure

//whentreesaredestructedthatallmemoryforallocatednodes

//isfreedup.

//clear();

}

/..;@returnsintReturnsthecurrentsizeofthisBinaryTree.

*/

intBinaryTree::size()const

{

returnnodeCount;

}

/..;@paramnodeTheBinaryTreeNodewearecurrentlyprocessing.

*

*@returnsstringReturnstheconstructedstringoftheBinaryTree

*contentsinascendingsortedorder.

*/

stringBinaryTree::tostring(BinaryTreeNode*node)const

{

//basecase,ifnodeisnull,justreturnemptystring,which

//stopstherecursing

if(node==NULL)

{

return"";

}

//generalcase,doaninordertraversalandbuildtring

else

{

ostringstreamout;

//doaninordertraversal

out<left)

<item<<""

<right);

returnout.str();

}

}

/..;@returnsstringReturnstheconstructedstringoftheBinaryTree

*contentsinascendingsortedorder.

*/

stringBinaryTree::tostring()const

{

ostringstreamout;

out<<"size:"<

<<"items:["<

returnout.str();

}

/..;@paramoutTheoutputstreamobjectweareinsertingastring/

*representationinto.

*@p..;@returnsostreamReturnsreferencetotheoutputstreamafter

*weinserttheBinaryTreecontentsintoit.

*/

ostream&operator<<(ostream&out,constBinaryTree&aTree)

{

out<

returnout;

}

ASS12/BinaryTree.hpp

#include 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); };