Computer Science City College of New York
Structures Fall 2016
Data Structures - Chapter 10 - Programming Assignment 6
The Bag Class with a Binary Search Tree
@ Data Structures and Other Objects Using C++
Implement the bag template class from Section 10.5, using a
binary search tree to store the items.
Ensure that you understand and can use binary search tree.
Read all of Chapter 10, especially Sections 10.3 and 10.5.
Monday, November 28, 2016. If you run into
hardware or software problems, you may submit on Wednesday with
no penalty. You may submit on Friday or Saturday with a small
penalty. No submissions will be accepted after Saturday.
How to Turn In:
Please submit homeworks using this link.
On the upload page, you can select the file(s) you want to
submit (multiple files can be selected by pressing down CTRL key
while selecting the files). Then enter your last name and the
last 4 digit of your student ID (from CUNYfirst, NOT your
SSN!!!). Once successfully submitted, it will show a page with
RECEIPT NUMBER, save that number or that page because you will
need it to retrieve your grade for that assignment. You can
submit your assignment as many times as you want before the
deadline, only the latest one will be graded.
Files that you must write and turn in :
To retrieve your grade for an assignment (after I finish grading
it), please go to the download page here,
select the assignment, enter the receipt number for that
assignment, your last name and your last 4 digit of your student
ID. The page will then download a TXT file which contain your
Other files that you may find helpful:
- bag6.h: Header file for this version of the bag
class. You don't have to write much of this file. Just copy our
version from bag6.h and add your name and
other information at the top.
- bag6.template: The implementation file for the new
bag class. I have written much of this to get you started. You
can download my starting file from bag6.template
NOTE: Some of you have been forgetting to put your name and a
clearly written invariant at the top of this file. I will start
taking off points for such omissions. In any case, there are four
functions in this implementation file that you must implement.
These files are marked with the words STUDENT WORK
- bintree.h: and bintree.template This is
the binary tree node template class from Section 10.3. You can
download them from bintree.h and bintree.template
NOTE:This version of the binary tree node has a small
change from the original version that appears in the first
printing of the second edition of the textbook ( and has a major
change from the version in the first edition of the book!). In
particular, the authors have changed the return values from the
non-const versions of the left() and right()
functions so that they return a reference to the pointer in the
node. This is indicated by the & symbol here:
binary_tree_node*& left( )
The use of a "reference" (indicated by the ampersand) in the
return value has two advantages that simplify the material of
In the case of tree_clear, this is not a huge advantage
because we could have just set p's left pointer to NULL ourselves.
But, in this assignment, there are two functions, bst_remove
and bst_remove_max, which are easier to write if we
can use p->left() and p->right() as
the parameters of recursive calls. See my implementations in
bag6.template for details.
- It now allows a direct assignment such as: p->left() =
NULL. This is not a huge advantage since the same thing can be
accomplished by using the set_left function.
- The expression p->left() can be passed as the
argument to a function such as: tree_clear(p->left());
The parameter of tree_clear is a reference
parameter, so that any changes that tree_clear makes
to p->left() will now affect the actual left
pointer in the node *p. In this example, the tree_clear
function does set its parameter to NULL, so that the total
effect of tree_clear(p->left()) is to clear the
left subtree of p and to set p's left pointer to NULL.
- bagtest.cxx: A simple
interactive test program.
- bagexam.cxx: A
non-interactive test program that will be used to grade the
correctness of your bag class.
The Bag Class Using a Binary Search Tree
Start by understanding the entire pseudocode for the binary search
tree operations (from Section 10.5). Then read through the portions
that I have already implemented for you. Implement the rest of your
work in two parts: (1) The insert and count functions, and (2) The
bst_remove_all and bst_remove_max functions. Don't move to step 2
until you have completely finished and tested step 1.
Discussion of the Assignment
Since this is a template class, debugging can be more difficult
(some debuggers don't permit breakpoints in a template function.
To help in debugging, you can call b.debug() in a program to print
the binary search tree for the bag b (using the format shown on
If you use a makefile, you must also be careful in specifying
what files are to be compiled. For example:
The bag and bintree templates are never compiled on their own, but
in order to create bagexam.o, all the template files must be present
in the current directory.
g++ -Wall -gstabs bagexam.o -o bagexam
bagexam.o: bagexam.cxx bag6.h bag6.template bintree.h bintree.template
g++ -c -Wall -gstabs bagexam.cxx
Most of your grade will be based on the correctness of your
implementation. However, I will also look at your work and assign
some points for clarity and programming style. Make sure that your
name is on all your work.
Feng HU (