Binary Search Tree

Given intbst.h and testbst.cpp, implement intbst.cpp to make a correct output (shown at the very end).

// intbst.h, don't change #ifndef INTBST_H #define INTBST_H class IntBST { public: // ctor, dtor, insert and one print method already done in intbst.cpp: IntBST(); // constructor ~IntBST(); // destructor bool insert(int value); // insert value; return false if duplicate void printPreOrder() const; // prints tree data pre-order to cout // 5 METHODS YOU MUST IMPLEMENT in intbst.cpp: void printInOrder() const; // print tree data in-order to cout void printPostOrder() const; // print tree data post-order to cout int sum() const; // sum of all values int count() const; // count of values bool contains(int value) const; // true if value is in tree // suggested signature of optional challenge method: // void remove(int value); // remove value from the tree private: // DO NOT CHANGE DEFINITION OF struct Node: struct Node { int info; Node *left, *right; // useful constructor: Node(int v=0) : info(v), left(0), right(0) { } }; // just one instance variable (pointer to root node): Node *root; // recursive utility functions for use by public methods above void clear(Node *n); // for destructor bool insert(int value, Node *n); // note overloading names for simplicity void printPreOrder(Node *n) const; void printInOrder(Node *n) const; void printPostOrder(Node *n) const; int sum(Node *n) const; int count(Node *n) const; bool contains(int value, Node *n) const; // not used for iterative solution // suggested signatures of utility functions for optional challenge: // void remove(int value, Node* &n); // uses removeThis below too // void removeThis(Node* &n); // in turn, uses maxValue below // int maxValue(Node *n) const; }; #endif 

// testbst.cpp, don't change #include "intbst.h" #include  using namespace std; int getTest(); // creates two trees (one of which is empty), // and does some simple tests of tree methods int main() { IntBST bst1, bst2; // insert data to bst1 bst1.insert(64); bst1.insert(128); bst1.insert(8); bst1.insert(512); bst1.insert(256); bst1.insert(32); bst1.insert(16); bst1.insert(4); // let user choose one or all tests bool all = true; int testnum = getTest(); if (testnum) all = false; // print and test methods for bst1 cout << "BST: " << endl << " pre-order: "; bst1.printPreOrder(); cout << endl; if (all || testnum == 1) { cout << " in-order: "; bst1.printInOrder(); cout << endl; } if (all || testnum == 2) { cout << " post-order: "; bst1.printPostOrder(); cout << endl; } if (all || testnum == 3) cout << " sum: " << bst1.sum() << endl; if (all || testnum == 4) cout << " count: " << bst1.count() << endl; if (all || testnum == 5) { cout << " contains 16? " << (bst1.contains(16) ? "Y" : "N") << endl; cout << " contains 128? " << (bst1.contains(128) ? "Y" : "N") << endl; cout << " contains 17? " << (bst1.contains(17) ? "Y" : "N") << endl; cout << " contains 512? " << (bst1.contains(512) ? "Y" : "N") << endl; } // test methods for empty bst2 cout << "Empty BST: " << endl << " pre-order: "; bst2.printPreOrder(); cout << endl; if (all || testnum == 1) { cout << " in-order: "; bst2.printInOrder(); cout << endl; } if (all || testnum == 2) { cout << " post-order: "; bst2.printPostOrder(); cout << endl; } if (all || testnum == 3) cout << " sum: " << bst2.sum() << endl; if (all || testnum == 4) cout << " count: " << bst2.count() << endl; if (all || testnum == 5) cout << " contains 16? " << (bst2.contains(16) ? "Y" : "N") << endl; // add tests for optional methods that you attempt to implement // but don't do that until after submitting the basic version return 0; } int getTest() { cout << "Choice of tests: " << " 0. all tests " << " 1. just printInOrder " << " 2. just printPostOrder " << " 3. just sum " << " 4. just count " << " 5. just contains "; do { int choice; cout << "Enter choice: "; cin >> choice; if (choice >=0 && choice < 6) return choice; cout << "0, 1, 2, 3, 4 or 5 only! "; } while (true); } 

// intbst.cpp, implement this // Implements class IntBST #include "intbst.h" #include  using std::cout; // constructor sets up empty tree IntBST::IntBST() : root(0) { } // destructor deletes all nodes IntBST::~IntBST() { clear(root); } // recursive helper for destructor void IntBST::clear(Node *n) { if (n) { clear(n->left); clear(n->right); delete n; } } // insert value in tree; return false if duplicate bool IntBST::insert(int value) { // handle special case of empty tree first if (!root) { root = new Node(value); return true; } // otherwise use recursive helper return insert(value, root); } // recursive helper for insert (assumes n is never 0) bool IntBST::insert(int value, Node *n) { if (value == n->info) return false; if (value < n->info) { if (n->left) return insert(value, n->left); else { n->left = new Node(value); return true; } } else { if (n->right) return insert(value, n->right); else { n->right = new Node(value); return true; } } } // print tree data pre-order void IntBST::printPreOrder() const { printPreOrder(root); } // recursive helper for printPreOrder() void IntBST::printPreOrder(Node *n) const { if (n) { cout << n->info << " "; printPreOrder(n->left); printPreOrder(n->right); } } // print tree data in-order, with helper void IntBST::printInOrder() const { printInOrder(root); } void IntBST::printInOrder(Node *n) const { // IMPLEMENT } // prints tree data post-order, with helper void IntBST::printPostOrder() const { printPostOrder(root); } void IntBST::printPostOrder(Node *n) const { // IMPLEMENT } // return sum of values in tree int IntBST::sum() const { return sum(root); } // recursive helper for sum int IntBST::sum(Node *n) const { return 0; // REPLACE THIS NON-SOLUTION } // return count of values int IntBST::count() const { return count(root); } // recursive helper for count int IntBST::count(Node *n) const { return 0; // REPLACE THIS NON-SOLUTION } // returns true if value is in the tree; false if not bool IntBST::contains(int value) const { return false; // REPLACE THIS NON-SOLUTION } //Correct Output  

Choice of tests: 0. all tests 1. just printInOrder 2. just printPostOrder 3. just sum 4. just count 5. just contains Enter choice: 0 BST: pre-order: 64 8 4 32 16 128 512 256 in-order: 4 8 16 32 64 128 256 512 post-order: 4 16 32 8 256 512 128 64 sum: 1020 count: 8 contains 16? Y contains 128? Y contains 17? N contains 512? Y Empty BST: pre-order: in-order: post-order: sum: 0 count: 0 contains 16? N