Implement a remove method to our OrderedSet class. Upload three files: OrderedSet.h, OrderedSet.cpp and a tester with main. Also upload a screenshot of you running program to show the tester output.

bool remove (int target);

// remove the node with target in it, if found, and return true (to signify that the removal succeeded). If target is not found, just return false.

// findParent is useful here, since in some cases we can just delete the child (the one that contains target) and update a pointer.

// Unfortunately, there is a special case where the node containing target has two children, so we can't just splice it out.

// Instead identify the parent of the node n with the smallest value v in the right subtree of the node containing the target.

// Then overwrite the value we want to remove with v and remove n. To remove n, update n's parent p so p->left = n->right.

// Also, avoid memory leak be deleting n after saving it's address to a temp.

#include #include using namespace std;

class Node { public: int value; Node* left, * right; Node(int v = 0, Node* l = nullptr, Node* r = nullptr) { value = v; left = l; right = r; } };

class OrderedSet { private: Node* r; int size;

static void preorder(Node* r) { // Fill this in to get preorder traversal. Output each value followed by a space. No endlines. if(r == nullptr) { return; } cout << r->value << " ";

preorder(r->left); preorder(r->right); }

static void postorder(Node* r) { // Fill this in to get postorder traversal. Output each value followed by a space. No endlines. if(r == nullptr) { return; }

postorder(r->left); postorder(r->right); cout << r->value << " "; }

static void inorder(Node* r) { // Fill this in to get inorder traversal. Output each value followed by a space. No endlines. if(r == nullptr) { return; }

inorder(r->left); cout << r->value << " "; inorder(r->right); }

// Return the r of a new BST, where the r value is a[length/2]. // left and right subtrees are obtained using appropriate recursive calls. // If length is 0 then return nullptr. Precondition: a sorted in ascending order static Node* makeBalancedTree(int a[], int length) { if (length > 0) { return new Node (a[length/2], makeBalancedTree(a, length/2), makeBalancedTree (a, length-(length/2)-1)); } // uncomment and complete in the line below // return new Node(a[length/2], makeBalancedTree( _____ ), makeBalancedTree( _____ ));

return nullptr; }

public: OrderedSet() { r = nullptr; size = 0; }

// precondition: a is sorted in ascending order

OrderedSet(int a[], int length) { r = makeBalancedTree(a, length); size = length; }

int getSize() const { return size; }

void levelorder() const { // Fill in to get a level order traversal. // If the tree is empty do nothing, other than output the endl. // Otherwise do the steps below. // Declare a local STL queue of template type Node* and // immediately push (enqueue) the r. // Now, as long as the queue is not empty, // get the Node at the front of the queue // and output its value followed by a space. // Also, push any (nonnull) children onto the queue, // in left to right order. pop (dequeue) the queue. if(r == nullptr) { cout << endl; return; } queue q; q.push(r); while(!q.empty()) { Node * temp = q.front(); q.pop(); cout << temp->value << " "; if(temp->left != nullptr) { q.push(temp->left); } if(temp->right != nullptr) { q.push(temp->right); } } cout << endl; }

void preorder() const { preorder(r); cout << endl; }

void inorder() const { inorder(r); cout << endl; }

void postorder() const { postorder(r); cout << endl; }

};

void test(const OrderedSet& s) { s.levelorder(); s.preorder(); s.inorder(); s.postorder(); cout << endl; }

int main() { int nums[100]; for (int i = 1; i <= 100; i++) nums[i-1] = i; int size; cin >> size; OrderedSet s(nums, size); test(s);

return 0; }