FOR PMY 1733 ONLY
Mesfer almesfer
wwageb.zipMMMM7.cbp
MA7.docx
CS 211 Micro Assignment #7
For this micro assignment, you must implement the following two functions inside BinarySearchTree.h:
int getHeight()
Returns the height of the tree. Note that you are allowed to solve this iteratively or recursively. If you go the recursive route, you'll probably need to create a helper function, similar to the tree's addElementHelper. Here's the relevant slide from the powerpoint presentation:
int getSize()
Grading
Your submission will be graded based on the following:
1. [7] Your solution passes the test cases
2. [3] Your code contains good style. For example,
· You provide meaningful variable names
· You provide sufficient and meaningful comments
· Your code is well structured
Due Date
This assignment must be submitted through Canvas no later than 1:00 PM on Tuesday, October 11, 2016. Submit your solution to Canvas in a ZIP file that contains all code and project files (either Visual Studio or Codeblocks).
image1.png
TreeNode (2).h
#ifndef TREE_NODE_H #define TREE_NODE_H template <typename T> class TreeNode { private: TreeNode<T> *_left_child = nullptr; TreeNode<T> *_right_child = nullptr; T _value; public: TreeNode(TreeNode<T> *left_child = nullptr, TreeNode<T> *right_child = nullptr) { _left_child = left_child; _right_child = right_child; } TreeNode<T> *getLeftChild() { return _left_child; } void setLeftChild(TreeNode<T> *child) { _left_child = child; } TreeNode<T> *getRightChild() { return _right_child; } void setRightChild(TreeNode<T> *child) { _right_child = child; } T getValue() { return _value; } void setValue(T value) { _value = value; } }; #endif // TREE_NODE_H
main (2).cpp
#include <iostream> #include <string> #include <vector> #include <queue> #include <initializer_list> #include "StringSplitter.h" #include "BinarySearchTree.h" using namespace std; void bstTest(initializer_list<int> values, int expected_height, int expected_size) { BinarySearchTree<int> bst{}; for (auto value : values) { bst.addItem(value); } cout << "Height: " << bst.getHeight() << " (expected: " << expected_height << ")" << endl; cout << "Size: " << bst.getSize() << " (expected: " << expected_size << ")" << endl; } int main() { bstTest({ 1, 2, 3, 4, 5 }, 4, 5); bstTest({ 5, 2, 3, 4, 1 }, 2, 5); bstTest({ 10, 7, 15, 12 }, 2, 4); return 0; }
StringSplitter (2).h
#ifndef STRING_SPLITTER_H #define STRING_SPLITTER_H #include <string> #include <vector> #include <queue> using namespace std; class StringSplitter { public: //Breaks apart the supplied text based on the given delimiter //static function do not affect the internal state //(e.g. variables) of a given class instance static queue<string> splitQ(string text, string delimiter) { //vectors are dynamically expanding arrays queue<string> pieces; //find the first delimiter int location = text.find(delimiter); //we are starting at the beginning of our string int start = 0; //go until we have no more delimiters while (location != string::npos) { //add the current piece to our list of pieces string piece = text.substr(start, location - start); pieces.push(piece); //update our index markers for the next round start = location + 1; location = text.find(delimiter, start); } //at the end of our loop, we're going to have one trailing piece to take care of. //handle that now. string piece = text.substr(start, location - start); pieces.push(piece); //now, return the completed vector return pieces; } }; #endif // STRING_SPLITTER_H
BinarySearchTree (2).h
#ifndef BINARY_SEARCH_TREE_H #define BINARY_SEARCH_TREE_H #include "TreeNode.h" /* Incomplete BST. We will fill this out more in future lectures. */ template <typename T> class BinarySearchTree { private: TreeNode<T> *_root = nullptr; protected: virtual TreeNode<T> *findLargestRec(TreeNode<T> *root) { //base case: root has no right child or root is null if (root == nullptr || root->getRightChild() == nullptr) { return root; } return findLargestRec(root->getRightChild()); } virtual TreeNode<T> *findLargestIter(TreeNode<T> *root) { while (root != nullptr || root->getRightChild() != nullptr) { root = root->getRightChild(); } return root; } virtual TreeNode<T> * addItemHelper(TreeNode<T> *root, T item) { //BASE CASE: null root if (root == nullptr) { //allocate new space, store value, then return. root = new TreeNode<T>{}; root->setValue(item); return root; } //RECURSIVE CASE: root is not null if (item >= root->getValue()) { //CASE 1: belongs on the right side of root TreeNode<T> *right = addItemHelper( root->getRightChild(), item ); //update right side with reconfigured state root->setRightChild(right); } else { //CASE 2: belongs on the left side of root TreeNode<T> *left = addItemHelper( root->getLeftChild(), item ); root->setLeftChild(left); } return root; } public: virtual void addItem(T value) { _root = addItemHelper(_root, value); } //MA #7 TODO: implement! //Gets the height of the tree. int getHeight() { return 0; } //MA #7 TODO: implement! //Note: You cannot use a "counter variable" to track height. Your function must //calculate the height manually (probably w/ recursion). int getSize() { return 0; } }; #endif // BINARY_SEARCH_TREE_H
