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

The Assignment:
  Implement the bag template class using a binary search tree to store the items. This assignment is a modified version
  of assignment found in the book

  "Data Structures and Other Objects Using C++" by Michael Main and Walter Savitch, ISBN 0-201-70297-5

Purposes:
  Ensure that you understand and can use binary search tree.
Due Dates:
  Part 1: (Insert and count functions) -- December 31, 2003
  Part 2: (The rest of the work) -- January 5, 2004
Files that you must write:
  1. `bag.h:` Header file for this version of the bag class. You don't have to write much of this file. A version is provided. Add your name and other information at the top.
  2. `bag.cpp:` The implementation file for the new bag class. I have written much of this to get you started.
     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:

1. `bintree.h:` and `bintree.cpp` This is the binary tree node template class files.

   NOTE: The functions`left()` and `right()` 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:
   - 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 the implementations in `bag.cpp` for details.
2. `bagtest.cpp:` A simple interactive test program.
3. `bagexam.cpp:` 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

A bag can be defined as a collection that groups elements with no particular positional relationship. A bag allows duplicates. Conceptually it is similar to a physical bag into which elements are placed, e.g., a shopping bag, a school bag for books.

Start by understanding the entire pseudocode for the binary search tree operations . 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.