CS211 Data Structures
The Assignment:
Implement the bag template class from Section 10.5, using a binary search tree to store the items.
Purposes:
Ensure that you understand and can use binary search tree.
Before Starting:
Read all of Chapter 10, especially Sections 10.3 and 10.5.
Due Dates:
Monday, December 3. If you run into hardware or software problems, you may submit on Tuesday with no penalty. You may submit on Wednesday with a small penalty. No submissions will be accepted after Wednesday.
How to Turn In:
Pack your files in a WinZip file (Windows) or tar file (Unix). Attach the file in your email with "CS211 Assignment 6" in your message Subject line, send it to me.
Files that you must write and turn in :
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
Other files that you may find helpful:
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 Chapter 10:
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.
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.
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 page 484).
If you use a makefile, you must also be careful in specifying what files are to be compiled. For example:
bagexam: bagexam.o
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
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.
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.