Binary Assign

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 ----------------

<constructor> Size of new empty tree: 0

5

size: 0 items: [ ]

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

<insert> Inserted into empty tree, size: 1

size: 1 items: [ 10 ]

<insert> inserted 5 more items, size: 6

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

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

<height> Current tree height: 3

<height> after inserting nodes, height: 5 size: 8

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

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

<clear> after clearing tree, height: 0 size: 0

size: 0 items: [ ]

Assignment Submission