Introduction
：
#include
using std::cout; using std::endl;
#include “BinarySearchTree.h”
#include “Set.h”
int main()
{
cout << “EMPTY MAIN” << endl;
}
：make test
Requirement
Project 2
100 points
Due Date: April 6 th 9:00PM
Project 2 Deliverables via Handin:
● BinarySearchTree.h
● Set.h
Remember you will be submitting only these 2 files via Handin.
Project submissions will always be through Handin.
This is not a team work, do not copy somebody else’s work.
Problem 1
Your job is to implement a standard binary search tree. You have to implement the following
public methods in your binary search tree. There are several private methods that also must be
used to implement these features in a recursive manner.
1. BinarySearchTree(); - No argument constructor, you can leave this as default
2. BinarySearchTree(vector values); - constructs the binary search tree and adds
every element of values to the tree.
3. ~BinarySearchTree(); - Must destroy every node of the tree. Use the void
destroy(Node node); method recursively to complete this task.
4. void add(T val); - Adds a val to the tree. If the val already exists in the tree, do not
modify the tree.
5. const T search(T val) const; - Returns a pointer to the value of the node if found.
Returns nullptr if the val is not found. Use const Node search(Node
root_node, T val) const; recursively to find the val using the standard binary
search algorithm.
6. void remove(T val); - Removes a val from the tree. You must account for all three
cases of removal: no children, 1 child, and 2 children. Use Node remove(Node
rootnode, T val); recursively to complete this task. This method returns the
new root node after the node is removed. (See class notes for additional reference). Note,
when the node to remove has two children, you must replace the removed node with the
minimum value in the removed node’s right subtree.
7. vector getValues() const; - Returns all elements of the tree in sorted order. Use
void inOrderTraversal(Node node, vector values) const; to
implement this functionality. For each node, add it to the vector values .
8. int size() const; - Returns the number of elements in the tree. Use int
size(Node node) const; recursively to implement this functionality.
Problem 2
A Set is an abstract data type that can store certain values, without any particular order, and no
repeated values. A Set can be implemented with a binary search tree, because in a BST, there are
no repeated values, and testing for membership in a BST is an O(log(n)) operation, which is
quite efficient. Your job is to implement a Set using the binary search tree you have created. For
information on this data type, consult the wikipedia page here:
(abstract_data_type) or the python documentation here:
You will need to complete the following methods on the Set class:
1. Set(vector values); - Construct a Set with all elements of values in it. If there are
duplicate items in values, only add them to the set once.
2. bool contains(T value) const; - Test value for membership in the set. Returns true
if value is in the set, false otherwise.
3. int size() const; - Returns the size of the set. Empty sets have size 0.
4. void add(T value); - Adds value to the set. If value is already in the set, do
nothing.
5. void remove(T value); - Removes value from the set. If value is not present in the
set, do nothing.
6. void clear(); - Removes all values in the set. One simple way to do this is to delete
the BST and construct a new one.
7. vector getValues() const; - Returns all values in the set. While by definition a
set is unordered, use the in-order traversal from the BST to produce a sorted output for
testing purposes.
8. bool isDisjoint(const Set other) const; - Return True if the set has no
elements in common with other . Sets are disjoint if and only if their intersection is the
empty set.
9. bool isSubset(const Set other) const; - Test whether every element in
the set is in other .
10. bool isSuperset(const Set other) const; - Test whether every element in
other is in this set.
11. Set unionWith(const Set other) const; - Return a new set with all
elements of the set and all elements of other . This new set will not have any duplicate
values.
12. Set intersection(const Set other) const; - Return a new set with
elements in the set that are in common with other .
13. Set difference(const Set other) const; - Return a new set with
elements in the set that are not in other .
14. Set symmetricDifference(const Set other) const; - Return a new
set with elements in either the set or in other, but not both.
Using the Makefile and Testing your work
You are provided with a Makefile. Run the project on the CSE server Black using
the commands below.
Makefile commands:
make
This will compile the code in main.cpp and generate an executable name
ProjectStackBST. Run this executable with the command ./ProjectStackBST
make test
This will run the tests for the project. These tests are only a subset of all tests and only
cover a few of the required methods. Passing all tests does not guarantee you will get all
the points. These are only public tests. Your code will be tested against these tests and
extra private tests.
Please make sure to have your tests sub folder in your project folder in order
to run the make test command successfully.
Reference: This project was created by the following incredible students. Scott
Swarthout author for the project and test cases. Fatema Alsaleh and Ibrahim
Ahmed authors of test cases.