CIS 11: Data Structures & Algorithms
Project I
Implement the bag template class from Section 10.5 of the text, using a binary search tree to store the items. This is the last bag. Really.
- Links to the files in the project:
- bag6.h: the header file for this version of the bag class.
- bag6.cpp: the implementation file for the new bag class. This is only partially completed and your job is to finish it. It is the only file you will submit.
- bintree.h and bintree.cpp: The binary tree node class from Section 10.3 of the textbook.
- bagtest.cpp: a simple interactive test program.
- bst_bag_test.cpp: a non-interactive test program that will be used to evaluate your implementation of the bag class.
- Start by understanding the entire pseudocode for the binary search tree operations (from Section 10.5). Then read through the portions that have already been implemented for you. Implement the rest of your work in two parts:
- first the insert() and count() functions,
- then the bst_remove_all() and bst_remove_max() functions.
When you're satisfied with the implementation, submit your work via the CATE
form for Project I.
Legend: method/function keyword literal
2007/04/05