Lab 5 (100 pts) Due Tuesday, May 10 as a hard copy in class and as a soft copy at 1pm on Catalyst Part 1: Complete the following BST functions:
#ifndef BST_H_ /**Private helper functions*/ void insert_value(Nodeptr root, bstdata value); //private helper function for insert //recursively inserts a value into the BST void inOrderPrint(Nodeptr root); //private helper function for inOrderPrint //recursively prints tree values in order from smallest to largest void preOrderPrint(Nodeptr root); //private helper function for preOrderPrint //recursively prints tree values in preorder
//private helper function for postOrderPrint //recursively prints tree values according in postorder public: //Instantiates a new BST //post: a new BST object bool is_empty(); //determines whether the BST is empty void insert(bstdata value); //inserts a new value into the BST //post: a new value inserted into the BST bstdata getRoot(); //returns the value stored at the root of the BST //pre: the BST is not empty void inOrderPrint(); //calls the inOrderPrint function to print out the values //stored in the BST
//calls the reOrderPrint function to print out the values //stored in the BST //calls the postOrderPrint function to print out the values //stored in the BST //more functions to be added here!
BST Functions: Insert
template <class bstdata> { } }
Pseudocode for insert_value(root, value) function 1. Base Case: the value to insert is equal to the data stored at the root If this is true, return 2. Check if the value to insert is smaller than the data stored at the root. 2a. If this is true 2aa. Check if root left is NULL 2aaa. If this is true, insert the value at root left 2b. If the root left is not NULL 2bb.recursively call the insert_value function passing it root left and value 3. Otherwise 3a. Check if the root right is NULL 3aa. If this is true, insert the value at root right 3b. If the root right is not NULL 3bb. recursively call the insert_value function passing it root right and value Testing Your Functions
cout << "Root of tree: " << bst.getRoot() << endl;
Part 2: Tree Traversals
inOrderPrint()
Pseudocode for inOrderPrint(root) 1. If the root is not NULL a. Call inOrderPrint recursively on the root left. b. Print the data at the root c. Call inOrderPrint recursively on the root right
Add preOrderPrint and postOrderPrint
Pseudocode for preOrderPrint(root) 1. If the root is not NULL a. Print the data at the root b. Call preOrderPrint recursively on the root left c. Call preOrderPrint recursively on the root right Pseudocode for postOrderPrint(root) 1. If the root is not NULL a. Call postOrderPrint recursively on the root left b. Call postOrderPrint recursively on the root right c. Print the data at the root
What to Submit
How You Will Be Graded
