Data Structures - Chapter 10 - Programming Assignment 6
The Bag Class with a Binary Search Tree

@ Data Structures and Other Objects Using C++ 

by Michael Main and Walter Savitch

Part 1: (Insert and count functions) Bonus if you finish and turn this in by Wednesday November 28, 2012. Part 2: (The rest of the work) Wednesday, December 05, 2012. If you run into hardware or software problems, you may submit on Thursday with no penalty. You may submit on Friday or Saturday with a small penalty. No submissions will be accepted after Saturday.

Pack your files in a WinZip file (Windows) or tar file (Unix). Attach the file in your email with "CSC212 Assignment 6" in your message Subject line, send it to Mr. Wai Khoo(WKhoo@gc.cuny.edu) and copy to me (zhu@cs.ccny.cuny.edu).

1. 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.
2. 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

1. 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 Chapter 10:
• 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.
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.
2. bagtest.cxx: A simple interactive test program.
3. 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
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 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

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.