C++ homework

A new Binary Search Tree was created with the following numerical key value input sequence ordering from left to right: 30, 56, 84, 96, 23, 25, 7, 60, 58, 82, 63, 83, 75, 61, 4, 27, 12, 24, 57, 87, 95, 99, and 59.

a. (2 points) Sketch the resulting binary search tree showing all its internal and external nodes in their proper hierarchical positions and their stored key values. Use a circle for each internal node and show its stored key value inside the circle. Use a solid square to represent each external node.

b. (2 points) Remove node holding key value 56 and sketch the resulting tree.

c. (2 points) From the original tree in step (a) above, remove node holding key value 60 and sketch the resulting tree.

d. (2 points) Referencing the textbook C++ example codes posted on our class github below:

// code from // Data Structures and Algorithms in C++, Goodrich, Tamassia, and Mount, 2nd Ed., 2011. // #pragma once #include "LinkedBinaryTree.h" template  class Entry { public: typedef K Key; typedef V Value; Entry(const Key &k = Key(), const Value &v = Value()) : _key(k), _value(v) {} const Key& key() const { return _key; } const Value& value() const { return _value; } void setKey(const Key& k) { _key = k; } void setValue(const Value& v) { _value = v; } private: Key _key; Value _value; }; template  class SearchTree { // a binary search tree public: // public types typedef typename E::Key K; // a key typedef typename E::Value V; // a value // class Iterator; // an iterator/position public: // public functions SearchTree(); // constructor int size() const; // number of entries bool empty() const; // is the tree empty? Position find(const K& k); // find entry with key k Position insert(const K& k, const V& x); // insert (k,x) void erase(const K& k); // remove key k entry //void erase(const Iterator& p); // remove entry at p // Iterator begin(); // iterator to first entry //Iterator end(); // iterator to end entry void printInorder() const; protected: // local utilities // BinaryTree BinaryTree; // linked binary tree //typedef typename BinaryTree::Position TPos; // position in the tree Position root() const; // get virtual root Position finder(const K& k, const Position& v); // find utility Position inserter(const K& k, const V& x); // insert utility void inorder(const Position& v) const; // inorder print utility Position eraser(Position& v); // erase utility // Position restructure(const TPos& v); // restructure private: // member data LinkedBinaryTree T; // the binary tree int n; // number of entries public: // ...insert Iterator class declaration here }; template  // constructor SearchTree::SearchTree() : T(), n(0) { T.addRoot(); } template  // get virtual root Position SearchTree::root() const { return T.root(); } template  int SearchTree::size() const // number of nodes { return n; } template  bool SearchTree::empty() const // is tree empty? { return size() == 0; } template  void SearchTree::printInorder() const // is tree empty? { cout << "Keys in order: "; inorder(root()); cout << endl; } template  void SearchTree::inorder(const Position& v) const // is tree empty? { if (v.isExternal()) return; inorder(v.left()); cout << (*v).key() << ", "; inorder(v.right()); } template  // find utility Position SearchTree::finder(const K& k, const Position& v) { if (v.isExternal()) return v; // key not found if (k < (*v).key()) return finder(k, v.left()); // search left subtree else if ((*v).key() < k) return finder(k, v.right()); // search right subtree else return v; // found it here } template  // find entry with key k Position SearchTree::find(const K& k) { return finder(k, root()); // search from root } template  // insert utility Position SearchTree::inserter(const K& k, const V& x) { Position v = finder(k, root()); // search from root if (!v.isExternal()) { // key already exists? (*v).setValue(x); // update value } else { T.expandExternal(v); // add new internal node (*v).setKey(k); (*v).setValue(x); // set entry n++; // one more entry } return v; // return insert position } template  // insert (k,x) Position SearchTree::insert(const K& k, const V& x) { return inserter(k, x); } template  // remove utility Position SearchTree::eraser(Position& v) { Position w; if (v.left().isExternal()) w = v.left(); // remove from left else if (v.right().isExternal()) w = v.right(); // remove from right else { // both internal? w = v.right(); // go to right subtree do { w = w.left(); } while (!w.isExternal()); // get leftmost node Position u = w.parent(); (*v).setKey((*u).key()); (*v).setValue((*u).value()); // copy w's parent to v } n--; // one less entry return T.removeAboveExternal(w); // remove w and parent } template  // remove key k entry void SearchTree::erase(const K& k) { Position v = finder(k, root()); // search from virtual root if (v.isExternal()) // not found? throw out_of_range("Erase of nonexistent key"); eraser(v); // remove it } 

Add a new function to print in reverse (descending) order.:

template

void SearchTree::printReverseorder() const

{ // add your codes here

}

You only need to show the codes for the function:

void SearchTree::printReverseorder() const

plus any required helper functions.