08 Jul Big Five and print-level-order on AVL tree
#ifndef AVL_TREE_H #define AVL_TREE_H #include “dsexceptions.h” #include <iostream> // For NULL #include <queue> // For level order printout #include <vector> #include <algorithm> // For max() function using namespace std; // AvlTree class // // CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds // // ******************PUBLIC OPERATIONS********************* // Programming Assignment Part I // bool empty( ) –> Test for empty tree @ root // int size( ) –> Quantity of elements in tree // int height( ) –> Height of the tree (null == -1) // void insert( x ) –> Insert x // void insert( vector<T> ) –> Insert whole vector of values // void remove( x ) –> Remove x (unimplemented) // bool contains( x ) –> Return true if x is present // Comparable findMin( ) –> Return smallest item // Comparable findMax( ) –> Return largest item // boolean isEmpty( ) –> Return true if empty; else false // void printTree( ) –> Print tree in sorted (in) order // void printPreOrder( ) –> Print tree in pre order // void printPostOrder( ) –> Print tree in post order // void printInOrder( ) –> Print tree in *in* order // Programming Assignment Part II (microassignment) // void makeEmpty( ) –> Remove and delete all items // void ~AvlTree( ) –> Big Five Destructor // AvlTree(const AvlTree &other) –> BigFive Copy Constructor // AvlTree(const AvlTree &&other) –> BigFive Move Constructor // AvlTree &operator= ( AvlTree & other ) –> Big Five Copy *assignment* operator // AvlTree &operator= ( AvlTree && other ) –> Big Five Move *assignment* operator // void printLevelOrder( ) –> Print tree in LEVEL order 🙂 // ******************ERRORS******************************** // Throws UnderflowException as warranted template <typename Comparable> class AvlTree { public: /** * Basic constructor for an empty tree */ AvlTree( ) : root( NULL ) { //cout << ” [d] AvlTree constructor called. ” << endl; } /** * Vector of data initializer (needed for move= operator rvalue) */ AvlTree( vector<Comparable> vals ) : root( NULL ) { insert(vals); } //******************************************************************************************* // START AVL TREES PART II – TODO: Implement // Other functions to look for include: clone, makeEmpty, printLevelOrder /** * Destroy contents of the AvlTree object – Big Five Destructor */ ~AvlTree( ) { //cout << ” [d] AvlTree Destructor called. ” << endl; // Empty out the AVL Tree and destroy all nodes (makeEmpty?) } /** * Copy other to new object – Big Five Copy Constructor */ AvlTree( const AvlTree &other ) : root( NULL ) { cout << ” [d] Copy Constructor Called.” << endl; // Copy contents of other to ourselves (maybe clone?) // Get a deep copy of other’s tree } /** * Move other’s tree to new object – Big Five Move Constructor */ AvlTree( AvlTree &&other ) : root( NULL ) { cout << ” [d] Move Constructor Called.” << endl; // *MOVE* the other’s tree to us // Don’t let other have the tree anymore (MINE!) } /** * Deep copy assignment operator – Big Five Copy *Assignment* Operator */ const AvlTree & operator= ( const AvlTree & other ) { cout << ” [d] Copy Assignment Operator Called.” << endl; // Ensure we’re not copying ourselves // Empty out ourselves // Get a deep copy of other’s tree return *this; // Return ourselves to caller } /** * Move assignment operator – Big Five Move *Assignment* Operator */ const AvlTree & operator= ( AvlTree && other ) { cout << ” [d] Move Assignment Operator Called.” << endl; // Don’t move ourselves into ourselves // Empty out ourselves // *MOVE* the other’s tree to us // Don’t let other have the tree anymore (MINE!) return *this; // Return ourselves to caller } /** * Make the tree logically empty. – Helper function! */ void makeEmpty( ) { makeEmpty( root ); } // END AVL TREES PART II //******************************************************************************************* /** * Find the smallest item in the tree. * Throw UnderflowException if empty. */ const Comparable & findMin( ) const { if( isEmpty( ) ) throw UnderflowException( ); return findMin( root )->element; } /** * Find the largest item in the tree. * Throw UnderflowException if empty. */ const Comparable & findMax( ) const { if( isEmpty( ) ) throw UnderflowException( ); return findMax( root )->element; } /** * Returns true if x is found in the tree. */ bool contains( const Comparable & x ) const { return contains( x, root ); } /** * Test if the tree is logically empty. * Return true if empty, false otherwise. */ bool isEmpty( ) const { return root == NULL; } /** * Return number of elements in tree. */ int size( ) { return size( root ); } /** * Return height of tree. * Null nodes are height -1 */ int height( ) { return height( root ); } /** * Print the tree contents in sorted order. */ void printTree( ) const { if( isEmpty( ) ) cout << “Empty tree” << endl; else printInOrder( root ); } /** * Print the tree contents in sorted order. */ void printInOrder( ) const { if( isEmpty( ) ) cout << “Empty tree” << endl; else printInOrder( root ); } /** * Print the tree contents in pre order. */ void printPreOrder( ) const { if( isEmpty( ) ) cout << “Empty tree” << endl; else printPreOrder( root ); } /** * Print the tree contents in post order. */ void printPostOrder( ) const { if( isEmpty( ) ) cout << “Empty tree” << endl; else printPostOrder( root ); } /** * Print tree in level order traversal. */ void printLevelOrder( ) const { if( isEmpty( ) ) cout << “Empty tree” << endl; else printLevelOrder( root ); } /** * Returns true if tree is empty */ bool empty( ) { return( root == NULL ); } /** * Insert x into the tree; duplicates are ignored. */ void insert( const Comparable & x ) { insert( x, root ); } /** * Insert vector of x’s into the tree; duplicates are ignored. */ void insert( vector<Comparable> vals) { for( auto x : vals ) { insert( x, root ); } } /** * Remove x from the tree. Nothing is done if x is not found. */ void remove( const Comparable & x ) { remove( x, root ); } /*****************************************************************************/ private: struct AvlNode { Comparable element; AvlNode *left; AvlNode *right; int height; AvlNode( const Comparable & theElement, AvlNode *lt, AvlNode *rt, int h = 0 ) : element( theElement ), left( lt ), right( rt ), height( h ) { } }; AvlNode *root; /** * Internal method to count nodes in tree */ int size( AvlNode * & t ) { return( (t == NULL) ? 0 : size( t->left ) + size( t->right ) + 1 ); /* if( t == NULL ) return(0); return( size( t->right, count ) + size( t->left, count ) + 1 ); */ } /** * Internal method to insert into a subtree. * x is the item to insert. * t is the node that roots the subtree. * Set the new root of the subtree. */ void insert( const Comparable & x, AvlNode * & t ) { if( t == NULL ) t = new AvlNode( x, NULL, NULL ); else if( x < t->element ) insert(x, t->left); else if( x > t->element ) insert(x, t->right); balance(t); } void balance( AvlNode * & t ) { if( t == NULL ) return; if( height( t->left ) – height( t->right ) == 2 ) { if( height( t->left->left ) >= height( t->left->right ) ) rotateWithLeftChild( t ); else doubleWithLeftChild( t ); } else if( height( t->right ) – height( t->left ) == 2 ) { if( height(t->right->right) >= height( t->right->left ) ) rotateWithRightChild( t ); else doubleWithRightChild( t ); } t->height = max( height( t->left ), height( t->right ) ) + 1; } /** * Remove node x from tree t */ void remove( const Comparable & x, AvlNode * & t ) { if( t == NULL ) return; if( x < t->element ) remove( x, t->left ); else if( t->element < x ) remove( x, t->right ); else if( t->left != NULL && t->right != NULL ) // Two children { t->element = findMin( t->right )->element; remove( t->element, t->right ); } else { AvlNode *oldNode = t; t = ( t->left != NULL ) ? t->left : t->right; delete oldNode; } balance( t ); } /** * Internal method to find the smallest item in a subtree t. * Return node containing the smallest item. */ AvlNode * findMin( AvlNode *t ) const { if( t == NULL ) return NULL; if( t->left == NULL ) return t; return findMin( t->left ); } /** * Internal method to find the largest item in a subtree t. * Return node containing the largest item. */ AvlNode * findMax( AvlNode *t ) const { if( t != NULL ) while( t->right != NULL ) t = t->right; return t; } /** * Internal method to test if an item is in a subtree. * x is item to search for. * t is the node that roots the tree. */ bool contains( const Comparable & x, AvlNode *t ) const { if( t == NULL ) return false; else if( x < t->element ) return contains( x, t->left ); else if( t->element < x ) return contains( x, t->right ); else return true; // Match } /****** NONRECURSIVE VERSION************************* bool contains( const Comparable & x, AvlNode *t ) const { while( t != NULL ) if( x < t->element ) t = t->left; else if( t->element < x ) t = t->right; else return true; // Match return false; // No match } *****************************************************/ /** * Internal method to make subtree empty. * TODO: Implement freeing all tree nodes */ void makeEmpty( AvlNode * & t ) { cout << ” [d] makeEmpty should walk the tree and free all nodes” << endl; // Walk tree, delete all nodes, set t to null } /** * Internal method to print a subtree rooted at t in sorted order. */ void printInOrder( AvlNode *t ) const { if( t != NULL ) { printInOrder( t->left ); cout << t->element << ” “; printInOrder( t->right ); } } /** * Internal method to print a subtree rooted at t in pre order. */ void printPreOrder( AvlNode *t ) const { if( t != NULL ) { cout << t->element << ” “; printPreOrder( t->left ); printPreOrder( t->right ); } } /** * Internal method to print a subtree rooted at t in post order. */ void printPostOrder( AvlNode *t ) const { if( t != NULL ) { printPostOrder( t->left ); printPostOrder( t->right ); cout << t->element << ” “; } } /** * Internal method to print tree t in level order traversal. * TODO: implement */ void printLevelOrder( AvlNode *t ) const { cout << ” [d] printing in level order not implemented” << endl; } /** * Internal method to clone subtree. * TODO: Likely a good thing for doing a deep copy */ AvlNode * clone( AvlNode *t ) const { // Check if t is null (can’t copy NULL? // Otherwise, Make a new AvlNode and clone t’s values recursively } // Avl manipulations /** * Return the height of node t or -1 if NULL. */ int height( AvlNode *t ) const { return t == NULL ? -1 : t->height; } int max( int lhs, int rhs ) const { return lhs > rhs ? lhs : rhs; } /** * Rotate binary tree node with left child. * For AVL trees, this is a single rotation for case 1. * Update heights, then set new root. */ void rotateWithLeftChild( AvlNode * & k2 ) { AvlNode *k1 = k2->left; k2->left = k1->right; k1->right = k2; k2->height = max( height( k2->left ), height( k2->right ) ) + 1; k1->height = max( height( k1->left ), k2->height ) + 1; k2 = k1; } /** * Rotate binary tree node with right child. * For AVL trees, this is a single rotation for case 4. * Update heights, then set new root. */ void rotateWithRightChild( AvlNode * & k1 ) { AvlNode *k2 = k1->right; k1->right = k2->left; k2->left = k1; k1->height = max( height( k1->left ), height( k1->right ) ) + 1; k2->height = max( height( k2->right ), k1->height ) + 1; k1 = k2; } /** * Double rotate binary tree node: first left child. * with its right child; then node k3 with new left child. * For AVL trees, this is a double rotation for case 2. * Update heights, then set new root. */ void doubleWithLeftChild( AvlNode * & k3 ) { rotateWithRightChild( k3->left ); rotateWithLeftChild( k3 ); } /** * Double rotate binary tree node: first right child. * with its left child; then node k1 with new right child. * For AVL trees, this is a double rotation for case 3. * Update heights, then set new root. */ void doubleWithRightChild( AvlNode * & k1 ) { rotateWithLeftChild( k1->right ); rotateWithRightChild( k1 ); } }; #endif
AvlTreeTesting.h
#include “AvlTree.h” #include <iostream> #include <string.h> /*****************************************************************************/ // Do lots of random inserts and deletes. This is a fuzzing test void test_BigTreeFuzzing() { /* BIGGER test of your AVL tree! */ cout << ” [t] Big Tree Fuzzing test.”; vector<int> incVals; AvlTree<int> bigTree; srand (time(NULL)); for( int i = 0; i < 3000; i++ ) { int newVal = rand() % 900000; // Generate new integer to insert into tree bool skip = false; for( int j = 0; j < incVals.size(); j++ ){ // Very dumb search! if( incVals[j] == newVal ){ skip = true; j = incVals.size(); } } if( !skip ){ bigTree.insert(newVal); incVals.push_back(newVal); } if( i % 3 == 0 ){ // Delete a random element every 3 inserts int remIndex = rand() % incVals.size(); bigTree.remove( incVals[remIndex] ); incVals.erase(incVals.begin() + remIndex); } } cout << ” – fuzzing test complete. ” << endl; } void test_empty() { AvlTree<int> myTree; cout << ” [t] Testing empty() interface”; if( myTree.empty() ) { cout << ” – Pass” << endl; } else { cout << ” – Fail” << endl; } } void test_size() { AvlTree<int> myTree; cout << ” [t] Testing size() interface…” << endl;; cout << ” [t] size() when empty: ” << myTree.size() << ” – “; (myTree.size() == 0) ? cout << “Pass” : cout << “Fail”; cout << endl; vector<int> vals = { 10, 5, 23, 3, 7, 30, 1 }; // Give us some data! myTree.insert( vals ); cout << ” [t] size() with ” << vals.size() << ” values: ” << myTree.size() << ” – “; (vals.size() == myTree.size()) ? cout << “Pass” : cout << “Fail”; cout << endl; myTree.remove( 10 ); // Remove the root, what about now? cout << ” [t] size() with ” << vals.size() – 1<< ” values: ” << myTree.size() << ” – “; (vals.size() – 1 == myTree.size()) ? cout << “Pass” : cout << “Fail”; cout << endl; } void test_height() { AvlTree<int> myTree; vector<int> vals = { 10, 5, 23, 3, 7, 30, 1 }; // Give us some data! cout << ” [t] Testing tree heights” << endl; cout << ” [t] Height of empty: ” << myTree.height() << ” – “; (myTree.height() == -1) ? cout << “Pass” : cout << “Fail”; cout << endl; myTree.insert(vals); cout << ” [t] Height of filled (3): ” << myTree.height() << ” – “; (myTree.height() == 3) ? cout << “Pass” : cout << “Fail”; cout << endl; } /* * Test printing tree in pre-, post-, and in- orders */ void test_prints() { AvlTree<int> myTree; vector<int> vals = { 10, 5, 23, 3, 7, 30, 1 }; // Give us some data! myTree.insert(vals); cout << ” [t] Testing tree print orders: ” << endl; cout << ” [t] In Order Target: \t1 3 5 7 10 23 30″ << endl; cout << ” [x] Tree In- Output: \t”; myTree.printInOrder(); cout << endl; cout << ” [t] Pre Order Target:\t10 5 3 1 7 23 30″ << endl; cout << ” [x] Tree Pre- Output:\t”; myTree.printPreOrder(); cout << endl; cout << ” [t] Post Order Target:\t1 3 7 5 30 23 10″ << endl; cout << ” [x] Tree Post- Output:\t”; myTree.printPostOrder(); cout << endl; } void test_insert() { AvlTree<int> myTree; cout << ” [t] Testing tree basic inserts: ” << endl; myTree.insert(20); myTree.insert(10); myTree.insert(5); // Forces right rotate cout << ” [t] Should be: \t10 5 20″ << endl; cout << ” [t] Pre Order: \t”; myTree.printPreOrder(); cout << endl; myTree.insert(30); myTree.insert(40); // Forces left rotate cout << ” [t] Should be: \t10 5 30 20 40″ << endl; cout << ” [t] Pre Order: \t”; myTree.printPreOrder(); cout << endl; myTree.insert(15); // Forces Right-Left double rotate cout << ” [t] Should be: \t20 10 5 15 30 40″ << endl; cout << ” [t] Pre Order: \t”; myTree.printPreOrder(); cout << endl; myTree.insert(13); myTree.insert(14); // Forces Left-Right double rotate cout << ” [t] Should be: \t20 10 5 14 13 15 30 40″ << endl; cout << ” [t] Pre Order: \t”; myTree.printPreOrder(); cout << endl; } void test_contains() { AvlTree<int> myTree; vector<int> vals = { 10, 5, 23, 3, 7, 30, 1 }; // Give us some data! myTree.insert( vals ); cout << ” [t] Testing contains:” << endl; cout << ” [t] Searching for: 7 (is in tree)”; (myTree.contains(7)) ? cout << ” – pass” : cout << ” – fail”; cout << endl; cout << ” [t] Searching for: 15 (not in tree)”; (!myTree.contains(15)) ? cout << ” – pass” : cout << ” – fail”; cout << endl; } /** * Testing the remove() function */ void test_remove() { AvlTree<int> myTree{ vector<int>{ 20, 10, 30, 5, 15, 25, 35, 1, 7, 13, 28, 3 } }; cout << ” [t] Testing remove():” << endl; cout << ” [x] Searching for: 7 (is in tree)”; (myTree.contains(7)) ? cout << ” – pass” : cout << ” – fail”; cout << endl; cout << ” [t] Pre order tree: “; myTree.printPreOrder(); cout << endl; cout << ” [t] Removing 7 from tree. ” << endl; myTree.remove(7); cout << ” [x] Searching for: 7 (is not in tree)”; (!myTree.contains(7)) ? cout << ” – pass” : cout << ” – fail”; cout << endl; cout << ” [t] Pre order target: 20 10 3 1 5 15 13 30 25 28 35″ << endl; cout << ” [x] Pre order tree: “; myTree.printPreOrder(); cout << endl; cout << ” [t] Removing 20 from tree. ” << endl; myTree.remove(20); cout << ” [t] Pre order target: 25 10 3 1 5 15 13 30 28 35″ << endl; cout << ” [x] Pre order tree: “; myTree.printPreOrder(); cout << endl; cout << ” [t] Removing 30 and 28 from tree. ” << endl; myTree.remove(30); myTree.remove(28); cout << ” [t] Pre order target: 10 3 1 5 25 15 13 35″ << endl; cout << ” [x] Pre order tree: “; myTree.printPreOrder(); cout << endl; } /** * Testing the copy constructor */ void test_copy_constructor() { AvlTree<int> myTree{ vector<int>{ 10, 5, 23, 3, 7, 30, 1 } }; cout << ” [t] Testing copy constructor:” << endl; AvlTree<int> treeCopy{ myTree }; // Calls copy constructor cout << ” [x] Source tree pre order: “; myTree.printPreOrder(); cout << endl; cout << ” [x] Tree COPY pre order: “; treeCopy.printPreOrder(); cout << endl; } /** * Testing the move constructor */ void test_move_constructor() { AvlTree<int> myTree{ vector<int>{ 10, 5, 23, 3, 7, 30, 1 } }; cout << ” [t] Testing move constructor:” << endl; cout << ” [x] Source tree pre order (before move): “; myTree.printPreOrder(); cout << endl; AvlTree<int> treeMove = std::move( myTree ); // Calls move constructor cout << ” [x] Source tree pre order (after move): “; myTree.printPreOrder(); cout << endl; cout << ” [x] Tree MOVE pre order: “; treeMove.printPreOrder(); cout << endl; } /* * Testing the copy *assignment* operator (copy=) */ void test_copy_assignment_op() { AvlTree<int> myTree{ vector<int>{ 10, 5, 23, 3, 7, 30, 1 } }; cout << ” [t] Testing copy assignment operator:” << endl; AvlTree<int> copy2; copy2 = myTree; // Calls copy assignment operator cout << ” [x] Source tree pre order: “; myTree.printPreOrder(); cout << endl; cout << ” [x] Dest tree pre order: “; copy2.printPreOrder(); cout << endl; } /* * Testing the move *assignment* operator (move=) */ void test_move_assignment_op() { vector<int> vals = { 10, 5, 23, 3, 7, 30, 22 }; // Give us some data! cout << ” [t] Testing move assignment operator:” << endl; AvlTree<int> treeMove; treeMove = AvlTree<int>{ vals }; // Calls move assignment operator cout << ” [x] Temp tree (rval) data (rotated): 10 5 3 7 23 22 30″ << endl;; cout << ” [x] New tree pre order (after move=): “; treeMove.printPreOrder(); cout << endl; } /* * Print tree out in level order. Tree should be: * 20 * 10 30 * 5 15 25 35 * 3 7 18 28 * 1 */ void test_print_level_order() { AvlTree<int> myTree{ vector<int>{ 20, 10, 30, 5, 15, 25, 35, 3, 7, 18, 28, 1 } }; cout << ” [t] Testing printing in level order:” << endl; cout << ” [t] Level Should be: 20 10 30 5 15 25 35 3 7 18 28 1″ << endl; cout << ” [x] Print Level Order: “; myTree.printLevelOrder(); cout << endl; } /* * Testing features of your AVL Tree implementation */ int avlTreeTests( bool fuzzing ) { cout << ” [x] Starting AVL tree test. ” << endl; test_empty(); // empty() interface working? test_size(); // size() interface working properly? test_height(); // height() working properly? test_prints(); // Print: preorder, postorder, inorder, levelorder test_insert(); // Insert test – all 4 types of rotates test_contains(); // Testing contains interface test_remove(); // Test of removing nodes via remove() if( fuzzing ) test_BigTreeFuzzing(); //Big tree fuzzing test cout << ” [x] Starting PART II tree tests. —————-” << endl; test_copy_constructor(); // Copy constructor tests test_move_constructor(); // Move constructor tests test_copy_assignment_op(); // Copy= operator tests test_move_assignment_op(); // Move= operator tests test_print_level_order(); // Print tree in LEVEL order return(0); }
dsexceptions.h
#ifndef DS_EXCEPTIONS_H #define DS_EXCEPTIONS_H class UnderflowException { }; class IllegalArgumentException { }; class ArrayIndexOutOfBoundsException { }; class IteratorOutOfBoundsException { }; class IteratorMismatchException { }; class IteratorUninitializedException { }; #endif
main.cpp
main.cpp
#include < iostream >
#include < cstdlib >
#include < string . h >
#include "AvlTree.h"
#include "AvlTreeTesting.h"
using namespace std ;
/*
* Main function for test or use
*/
int main ( int argc , char * argv [] )
{
int retState = 0 ;
// Note: If you call this program like this: ./avltree --test
// it will call the test function
if ( argc > 1 && ! strcmp ( argv [ 1 ], "--test" ) )
{
cout << " [x] Running in test mode. " << endl ;
bool withFuzzing = false ;
withFuzzing = ( argc > 2 && ! strcmp ( argv [ 2 ], "--withFuzzing" ) ); // Test for fuzzing option
retState = avlTreeTests ( withFuzzing ); // From AvlTreeTesting.h
cout << " [x] Program complete. " << endl ;
}
else
{
cout << " [x] Running in normal mode. " << endl ;
cout << " [!] Nothing to do in normal mode so here's a helicopter: " << endl ;
cout << " ___.___\n (_]===*\n o 0" << endl ;
cout << endl << " You should probably run 'make test' to test your program. " << endl ;
cout << " This program also has a fuzzing test with 'make bigtest' to test your program. " << endl ;
}
return ( retState );
}
Makefile
# # # # Variables GPP = g++ CFLAGS = -g -std=c++0x RM = rm -f BINNAME = avltree # Shell gives make a full user environment # Adding this to PATH will find the newer g++ compiler on the EECS servers. SHELL := /bin/bash PATH := /opt/rh/devtoolset-3/root/usr/bin/:$(PATH) # Default is what happenes when you call make with no options # In this case, it requires that ‘all’ is completed default: all # All is the normal default for most Makefiles # In this case, it requires that build is completed all: build # build depends upon *.cpp, then runs the command: # g++ -g -std=c++0x -o bigFiveList build: main.cpp $(GPP) $(CFLAGS) -o $(BINNAME) main.cpp run: build ./$(BINNAME) test: build ./$(BINNAME) –test bigtest: build ./$(BINNAME) –test –withFuzzing # If you call “make clean” it will remove the built program # rm -f HelloWorld clean veryclean: $(RM) $(BINNAME)
MA3-AVLII-BigFiveandLevelOrder.pdf
CptS 223 Micro Assignment #3 – AVL Big Five + Level Order Tree Print
For this micro assignment, you will be starting with a working AVL tree. Your task is to implement the
C++11 big five, just as you did for the linked list microassignment. Additionally, you will need to
implement a new print function for the tree: printLevelOrder. The included source for the AVL tree is
fully functional up to the Big Five and Level Order stages. The six functions you’ll need are well
delineated in the file AvlTree.h.
I’ve stubbed in the Big Five and printLevelOrder. There are new tests in the AvlTreeTesting.h file to
cover these in the API. As you complete them, the tests should start outputting the correct data. The
Big Five should be very similar to our linked list project, but with fewer values to copy/preserve. The
more interesting solution will actually be in printLevelOrder.
Printing a tree in level order means printing each level from left to right, then proceeding down to the
next level. This is best done with a queue-based solution instead of the stack based ones we’ve seen
before. Your solution MUST use the C++ STL queue class. The solution is easiest done with a loop
instead of recursion.
The code must compile and run on the EECS servers using g++. Like usual, I have provided a Makefile
to build and test the code. To just build your code, execute ‘make’. To run the test suite, run ‘make
test’. The tests are getting long now, so the first ones will scroll off of the top of the terminal. If you
want to learn a great tool to look at and scroll through the output, look up the Linux command “less”.
I found myself doing this command: ‘make test | less’. That will let you look at the output without
having to scroll back up the terminal. less is a great tool for looking at and searching through files, too.
Grading Your submission will be graded based on the following:
1. [8] Your modifications cause no runtime issues, your Big Five and PrintLevelOrder prints out
the proper results as shown in the tests when you run make test.
2. [2] Your modifications contain 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 as a zip or tar.gz file containing your source code through
Blackboard no later than 11:59pm on Friday, March 10th, 2017. Remember, you’re more than welcome to turn it in early instead of working on it the first night of Spring Break, but that’s your call.
Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.
Fill in all the assignment paper details that are required in the order form with the standard information being the page count, deadline, academic level and type of paper. It is advisable to have this information at hand so that you can quickly fill in the necessary information needed in the form for the essay writer to be immediately assigned to your writing project. Make payment for the custom essay order to enable us to assign a suitable writer to your order. Payments are made through Paypal on a secured billing page. Finally, sit back and relax.
About Writedemy
We are a professional paper writing website. If you have searched a question and bumped into our website just know you are in the right place to get help in your coursework. We offer HIGH QUALITY & PLAGIARISM FREE Papers.
How It Works
To make an Order you only need to click on “Order Now” and we will direct you to our Order Page. Fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.
Are there Discounts?
All new clients are eligible for 20% off in their first Order. Our payment method is safe and secure.