/** @file BinaryTree.hpp
* @brief Header file with class definition 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 class ADT data structure. You need to add the member function
* prototypes to this file for this assignment.
*/
#include
using namespace std;
#ifndef BINARYTREE_HPP
#define BINARYTREE_HPP
/** 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.
*/
struct BinaryTreeNode
{
/// @brief 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.
int item;
/// @brief Pointer to the left child of this node. This is NULL if there
/// is currently no left child of this node. If both left and right
/// are NULL then this node is a leaf node.
BinaryTreeNode* left;
/// @brief Pointer to the right child node of this node. This is NULL if
/// there is currently no right child of this node. If both left and right
/// are NULL then this node is a leaf node.
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.
*/
class BinaryTree
{
private:
/// @brief 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.
BinaryTreeNode* root;
/// @brief The count of the number of nodes/items currently in this
/// binary tree.
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, height, clear, add function prototypes here
// tree traversal and display
string tostring() const;
friend ostream& operator<<(ostream& out, const BinaryTree& aTree);
};
#endif // BINARYTREE_HPP
—
title: ‘Assignment 11: Binary Search Trees’
author: ‘COSC 2336: Data Structures and Algorithms’
date: ‘Fall 2020’
—
# 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`
implementation 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 Shaffer BSTNode (pg. 156,161)
and the BST abstract class and linked pointer implementation
(Shaffer pg. 171), but we will define our own version and simplify
some of the functions and interface.
You have been given a `BinaryTree.[cpp|hpp]` file that defines
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.
# Setup
For this assignment you will be given the following files:
| File Name | Description |
|--------------------|-----------------------------------------------------|
| `assg11-tests.cpp` | Unit tests for the member functions and queue |
| | functions you are to write. |
| `BinaryTree.hpp` | Header file for the BinaryTree class that |
| | that you are to add function prototypes for the |
| | new member functions into. |
| `BinaryTree.cpp` | Implementation file, the implementation of the |
| | BinaryTree class member methods for this assignment |
| | go here in this file. |
Set up a multi-file project to compile the `.cpp` source files
and run them as shown for the class. The Makefile you were
given should be usable to create a build project using the Atom editor
as required in this class.
The general approach you should take for this assignment, and all
assignment is:
1. Set up your project with the given starting code. The files
should compile and run, but either no tests will be run, or tests
will run but be failing.
2. For this project, start by uncommenting the first `TEST_CASE` in
the `assg11-tests.cpp` file. These are the unit tests to test the
functionality of your `BinaryTree` `insert()` function, the
class recursive method you are to implement.
3. Add the `insert()` public and private prototypes to the `BinaryTree.hpp` header file.
4. Add a stub for your two `insert()` member function to the
`BinaryTree.cpp` implementation file. The public `insert()` is a void function so
it can initially be empty. The private version of the function should return
a pointer to a `BinaryTreeNode`, so you should create a new node and return it
initially from this function.
5. Your code should compile and run now. Make sure after adding the
public and private stub methods your code compiles and runs. However,
your unit tests will be failing initially.
6. Incrementally implement the functionality of your
`insert()` member functions. Most of the work is actually done by the
private `insert()` function. You should try to add no more than 2
or 3 lines of code, and then make sure your program still compiles
and runs. Start by adding code to get the first failing test to
pass. Then once that test passes, move on to the next failing
tests until you have all tests passing. If you write something
that causes a previously passing test to fail, you should stop and
figure out why, and either fix it so that the original test still
passes, or remove what you did and try a new approach.
7. Once you have the `insert()` member function implemented and all
unit tests passing, you should then move on to the other functions
in the order suggested. Some functions use previous ones in this
assignment, so do them in the order given for you in the tasks
below.
# Tasks
You should set up your project/code as described in the previous
section. In this section we give some more details on implementing
the member functions for this assignment. You should perform the following
tasks for this assignment:
1. In order to test your class, we first 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
functions for your `BinaryTree` will have a public function
that asks as the interface that is called by users of the
`BinaryTree`, and a private version that actually does the
work using a recursive algorithm. I will give you the
signature you need for the `insert()` functions:
```c
class BinaryTree
{
private:
BinaryTreeNode* insert(BinaryTreeNode* node, const int item);
public:
void insert(const int item);
}
```
Lets start first 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 first 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 first parameter.
Of course, in the case that the item is greater than the one in
the current `node`, you instead need to call `insert()` on the
`node->right` child subtree.
And finally, make sure you take care of correctly returning
a result from the recursive `insert()`. Here when you call
`insert()` on either 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 assigned 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 result should be assigned back into
`node->right`. Again this is because when we finally find 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 assign the
returned pointer back into either `node->left` or `node->right`
appropriately. And finally, 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 fine 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 finally, 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
definition of the height of a tree.
`height()` needs 2 functions again, a public function which is
the interface, and a private function that is recursive and does
the actual work. Both the public and private `height()` functions
should be declared 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 conceptual 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, find the maximum of these two, add 1 to it, and that is the
height of the `node`.
3. The third and final 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 public `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 first. 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`.
# Example Output
Here is the correct output you should get from your program
if you correctly implement all the class functions and successfully
pass all of the unit tests given for this assignment. If you
invoke your function with no command line arguments, only failing
tests are usually shown by default. In the second example, we use the
-s command line option to have the unit test framework show both
successful and failing tests, and thus we get reports of all of the
successfully passing tests as well on the output.
“`
$ ./test
===============================================================================
All tests passed (40 assertions in 4 test cases)
$ ./test -s
——————————————————————————-
test is a Catch v2.7.2 host application.
Run with -? for options
——————————————————————————-
test basic BinaryTree functionality
——————————————————————————-
assg11-tests.cpp:30
…………………………………………………………………….
assg11-tests.cpp:35: PASSED:
CHECK( t.size() == 0 )
with expansion:
0 == 0
… output snipped …
===============================================================================
All tests passed (40 assertions in 4 test cases)
“`
# Assignment Submission
A MyLeoOnline submission folder has been created for this assignment.
For these assignments I do not need the test files, nor do I need your
visual studio project files or a whole zip/archive of your project
directory. For this assignment you have 2 files to submit:
`BinaryTree.hpp`, `BinaryTree.cpp`. These should be the only files
you added code into (besides uncommenting tests in the test file).
Also make sure that the names are the same as originally given to you
(do not rename them Assignment or Program01, etc., do not change assg
to Assg, make sure the case of the file names is CamelCaseNotation).
A large portion of your programs will be tested automatically, so
keeping the files names the same and making sure your code passes the
unit tests as given to you is important for being able to grade your
submission.
A MyLeoOnline submission folder has been created for this assignment.
There is a target named `submit` that will create a tared and gziped
file named `assg02.tar.gz`. You should do a `make submit` when finished
and upload your resulting gzip file to the MyLeoOnline Submission
folder for this assignment.
“`
$ make submit
tar cvfz assg11.tar.gz assg11-tests.cpp assg11-main.cpp BinaryTree.hpp BinaryTree.cpp
assg11-tests.cpp
assg11-main.cpp
BinaryTree.hpp
BinaryTree.cpp
“`
# 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 satisfied.
1. (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.
1. (30 pts.) `height()` functionality is implemented correctly.
Correctly implement stated base and general cases using recursion.
1. (30 pts.) `clear()` functionality is implemented correctly.
Correctly implement stated base and general cases using recursion.
1. (10 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. You should rewrite the unit tests to use your
template class, and submit your rewritten tests. You will need
to modify your header and Makefile build to build using a template
rather than a separately compilable file. If you do this, submit
your code first of the working non-templatized `BinaryTree.[hpp|cpp]`
files.
1. (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 offset 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 first visiting our right,
then ourself, then our left child.
1. (10 pts. extra credit) The `BinaryTree` is missing a big piece of
functionality, 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
Shaffer 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 figure 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 files, and
only 2 spaces used for indentation.
1. A function header must be present for member functions you define.
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.
1. You should have a document header for your class. The class header
document should give a description of the class. Also you should
document all private member variables that the class manages in the
class document header.
1. 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
specific to a single operating system, such as the
`system(“pause”)` which is Microsoft Windows specific.
/** @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
#include
#include
#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;
}
Assignment
1
1: Binary Search Trees
COSC
2
3
3
6
: Data Structures and Algorithms
Fall 2020
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 implementation 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 Shaffer BSTNode (pg. 1
5
6,161) and the BST
abstract class and linked pointer implementation (Shaffer pg. 171), but we will define our own version and simplify
some of the functions and interface.
You have been given a BinaryTree.[cpp|hpp] file that defines 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.
Setup
For this assignment you will be given the following files:
File Name Description
assg11-tests.cpp Unit tests for the member functions and queue
functions you are to write.
BinaryTree.hpp Header file for the BinaryTree class that
that you are to add function prototypes for the
new member functions into.
BinaryTree.cpp Implementation file, the implementation of the
BinaryTree class member methods for this assignment
go here in this file.
Set up a multi-file project to compile the .cpp source files and run them as shown for the class. The Makefile you
were given should be usable to create a build project using the Atom editor as required in this class.
The general approach you should take for this assignment, and all assignment is:
1. Set up your project with the given starting code. The files should compile and run, but either no tests will be
run, or tests will run but be failing.
2. For this project, start by uncommenting the first TEST_CASE in the assg11-tests.cpp file. These are the unit
tests to test the functionality of your BinaryTree insert() function, the class recursive method you are to
implement.
1
3. Add the insert() public and private prototypes to the BinaryTree.hpp header file.
4
. Add a stub for your two insert() member function to the BinaryTree.cpp implementation file. The public
insert() is a void function so it can initially be empty. The private version of the function should return a
pointer to a BinaryTreeNode, so you should create a new node and return it initially from this function.
5. Your code should compile and run now. Make sure after adding the public and private stub methods your code
compiles and runs. However, your unit tests will be failing initially.
6. Incrementally implement the functionality of your insert() member functions. Most of the work is actually
done by the private insert() function. You should try to add no more than 2 or 3 lines of code, and then
make sure your program still compiles and runs. Start by adding code to get the first failing test to pass. Then
once that test passes, move on to the next failing tests until you have all tests passing. If you write something
that causes a previously passing test to fail, you should stop and figure out why, and either fix it so that the
original test still passes, or remove what you did and try a new approach.
7. Once you have the insert() member function implemented and all unit tests passing, you should then move
on to the other functions in the order suggested. Some functions use previous ones in this assignment, so do
them in the order given for you in the tasks below.
Tasks
You should set up your project/code as described in the previous section. In this section we give some more details on
implementing the member functions for this assignment. You should perform the following tasks for this assignment:
1. In order to test your class, we first 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 functions for your BinaryTree will have a public function that asks as the interface that is called
by users of the BinaryTree, and a private version 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 first 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 first 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 <=
2
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 first parameter. Of course, in the case that the item is
greater than the one in the current node, you instead need to call insert() on the node->right child subtree.
And finally, make sure you take care of correctly returning a result from the recursive insert(). Here when
you call insert() on either 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 assigned 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 result should be assigned back into node->right. Again this is because when we
finally find 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 assign the returned pointer
back into either node->left or node->right appropriately. And finally, 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 fine 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 finally, 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 definition of the height of a tree.
height() needs 2 functions again, a public function which is the interface, and a private function that is
recursive and does the actual work. Both the public and private height() functions should be declared 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 conceptual 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, find the maximum of these two, add 1 to it, and that is
the height of the node.
3. The third and final 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 public 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.
3
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 first. 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.
Example Output
Here is the correct output you should get from your program if you correctly implement all the class functions and
successfully pass all of the unit tests given for this assignment. If you invoke your function with no command line
arguments, only failing tests are usually shown by default. In the second example, we use the -s command line option
to have the unit test framework show both successful and failing tests, and thus we get reports of all of the successfully
passing tests as well on the output.
$ ./test
===============================================================================
All tests passed (40 assertions in 4 test cases)
$ ./test -s
——————————————————————————-
test is a Catch v2.7.2 host application.
Run with -? for options
——————————————————————————-
test basic BinaryTree functionality
——————————————————————————-
assg11-tests.cpp:30
…………………………………………………………………….
assg11-tests.cpp:35: PASSED:
CHECK( t.size() == 0 )
with expansion:
0 == 0
… output snipped …
===============================================================================
All tests passed (40 assertions in 4 test cases)
Assignment Submission
A MyLeoOnline submission folder has been created for this assignment. For these assignments I do not need the
test files, nor do I need your visual studio project files or a whole zip/archive of your project directory. For this
assignment you have 2 files to submit: BinaryTree.hpp, BinaryTree.cpp. These should be the only files you added
code into (besides uncommenting tests in the test file). Also make sure that the names are the same as originally
given to you (do not rename them Assignment or Program01, etc., do not change assg to Assg, make sure the case of
the file names is CamelCaseNotation). A large portion of your programs will be tested automatically, so keeping the
files names the same and making sure your code passes the unit tests as given to you is important for being able to
grade your submission. A MyLeoOnline submission folder has been created for this assignment. There is a target
named submit that will create a tared and gziped file named assg02.tar.gz. You should do a make submit when
4
finished and upload your resulting gzip file to the MyLeoOnline Submission folder for this assignment.
$ make submit
tar cvfz assg11.tar.gz assg11-tests.cpp assg11-main.cpp BinaryTree.hpp BinaryTree.cpp
assg11-tests.cpp
assg11-main.cpp
BinaryTree.hpp
BinaryTree.cpp
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 satisfied.
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. (10 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. You should rewrite the unit
tests to use your template class, and submit your rewritten tests. You will need to modify your header and
Makefile build to build using a template rather than a separately compilable file. If you do this, submit your
code first of the working non-templatized BinaryTree.[hpp|cpp] files.
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 offset 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 first visiting our right, then ourself, then our left child.
7. (10 pts. extra credit) The BinaryTree is missing a big piece of functionality, 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 Shaffer 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 figure 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 files, and only 2 spaces used for indentation.
2. A function header must be present for member functions you define. 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
5
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 document 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 specific to a single operating
system, such as the system(“pause”) which is Microsoft Windows specific.
6
Objectives
Description
Setup
Tasks
Example Output
Assignment Submission
Requirements and Grading Rubrics
Program Execution, Output and Functional Requirements
Program Style
