COSC 160 Project 2

COSC 160: Data Structures

Project 2
Fall 2021

Due: F 10/1 @ 5 PM
9 points

This project involves implementing a binary search tree. Instead of storing key-value pairs, as we did with Hashtable<K,V,H>, we will store only keys and no values (or satellite data).

In addition to insert, remove, and find methods, you will also implement methods for copying and clearing trees. You will implement a method that returns a list of positions in the tree constructed using a preorder traversal. You will also implement an iterator that visits entries using an inorder traversal. Note that when removing a key from a node with two children, remove must promote the minimum key in the right subtree.

I put some starter code on cs-class-1, which you can retrieve using the command:

cs-class-1% cp ~maloofm/cosc160/p2.zip ./

As with previous projects, test your implementation of the BSTree<T> class in main.cc. We will use our own main function to evaluate your class. You must not modify the class name or the public interface. Our main.cc will include only main.h, so put all necessary includes there. You will need to declare additional private methods. Use the Makefile from the previous project with the appropriate modifications.

Instructions for Electronic Submission: In a file named HONOR, please include the statement:

In accordance with the class policies and Georgetown's Honor Code,
I certify that, with the exceptions of the class resources and those
items noted below, I have neither given nor received any assistance
on this project.

Include this file in your zip file submit.zip.

Submit p2 exactly like you submitted p1. Make sure you remove all debugging output before submitting.

Plan B

If something goes wrong with Autolab, upload your zip file to Canvas.