Description
The Assignment:
Implement the bag template class using a binary search tree to store the items.
Binary Search Tree (BST) storage rules:
• The entry in node n is never less than an entry in its left subtree (though it may be
equal to one of these entries)
• The entry in node n is less than every entry in its right subtree
BSTs also can store a collection of strings, or real numbers, or anything that can be compared
using some sort of less-than comparison. This provides higher search efficiency compared to
the implementations using array or linked-list. The higher efficiency of searching in a BST
motivates us to implement the bag class with a BST.
Invariants:
• The items in the bag are stored in a binary search tree
• The root pointer of the binary search tree is stored in the member variable root_ptr
(which may be NULL for an empty tree)
Refer to Slide Set 10 for the explanation of this assignment and its relevant functions.
Files that you must complete:
1. bag_bst.h
2. bintree.h
Other files that you may find helpful:
1. bagtest.cpp: A simple interactive test program.
2. bagexam.cpp: A test program that will be used to grade the correctness of your bag
class.
