Need help with C++ code please

Part One:

Complete missing functions in bst.cpp. You can use main.cpp to test.

//bst.cpp code below

#include "bst.h" #include #include

BST* makeBST() { BST* B = new BST(); B->root = NULL; return B; }

Node* getRoot(BST* T) { return T->root; }

void insert(int value, BST* T) { T->root = insert_value(value,T->root); }

bool find(int value, BST* T) { return find_value(value, T->root); }

void delete_from_tree(int value, BST* T) { T->root = delete_value(value,T->root); }

int min(BST* T) { return find_min(T->root); }

void inorder(BST* T) { inorder_walker(T->root); std::cout << std::endl; }

void preorder(BST* T) { preorder_walker(T->root); std::cout << std::endl; }

void postorder(BST* T) { postorder_walker(T->root); std::cout << std::endl; }

int height(BST* T) { return node_height(T->root); }

//You have to start implementing from here down

//Do a walk starting at the node given //Print the results to cout //Print N for nulls //Print a space after each value //Print out an N for null positions void inorder_walker(Node* current) { //Implement me return; } void preorder_walker(Node* current) { //Implement Me return; } void postorder_walker(Node* current) { //Implement Me return;

}

//Insert value v starting at node current Node* insert_value(int v, Node* current) { //Implement me return current; }

//Find value starting at current node bool find_value(int value, Node* current) { //Implement Me return false; }

//Find the min of the tree starting at current node //Return -1 on current is null int find_min(Node* current) { //Implement Me return -1; }

//Determine the node height of the current node //Hint: The height of a null is -1 int node_height(Node* current) { //Implement Me return -1; }

//I will provide you with delete Node* delete_value(int v, Node* current) { if(current==NULL){ return NULL; }else if(current->value == v){ Node* x = delete_node(current); return x; }else if(current->value > v){ current->left=delete_value(v,current->left); return current; }else{ current->right=delete_value(v,current->right); return current; } } Node* delete_node(Node* current) { if(current->left == NULL){ return current->right; } if(current->right==NULL) { return current->left; } int minval = find_min(current->right); current->value = minval; current->right = delete_value(minval,current->right); return current; }

=============================================

//bst.h code below

//Struct and Operators for a BST

#ifndef BST_LIBRARY_H #define BST_LIBRARY_H

//A Data Structure to store a node struct Node { int value; Node* left; Node* right; };

//A Data Structure for a BST struct BST { Node* root; };

//Constructor //Creates and returns a new BST BST* makeBST();

//Get Root //This function returns a pointer to the root node //It will be useful to implement later functions //You may assume T is not null Node* getRoot(BST* T);

//Primary Operations //Insert value into tree void insert(int value, BST* T);

//Find a value in the tree bool find(int value, BST* T);

//Delete a value void delete_from_tree(int value, BST* T);

//Find the min of the tree int min(BST* T);

//Prints //These will print directly to cout. //Print Inorder void inorder(BST* T); //Prints Preorder void preorder(BST* T); //Prints Postorder void postorder(BST* T);

//Determine the height int height(BST* T);

//Helpers needed for recursion void inorder_walker(Node* current); void preorder_walker(Node* current); void postorder_walker(Node* current);

//Insert Helper Node* insert_value(int v, Node* current); //Find Helper bool find_value(int value, Node* current); //Find the min starting at node current int find_min(Node* current); //Find Height of a Node int node_height(Node* current); //Delete Helper Node* delete_value(int v, Node* current); Node* delete_node(Node* current);

#endif

========================================

//main.cpp code below

#include "bst.h" #include //For printing #include //For null pointers #include //For formatting #include //For Random Numbers #include //To find out what time it is void test_insert(int v, BST* B); void test_delete(int v, BST* B); int single_experiment(int n); void run_experiment();

int main(){ //Set up the random number generator srand(time(0));

//First we do some simple examples. BST* B = makeBST(); //Insert some numbers to make an expected tree test_insert(6,B); test_insert(4,B); test_insert(1,B); test_insert(10,B); test_insert(8,B); test_insert(5,B); test_insert(12,B); //Check the height std::cout << "The Tree Height is " << height(B) << std::endl; //Check find for(int i=0; i < 13; i++) { std::cout << "Is " << i << " in the tree? " << std::endl; std::cout << find(i,B) << std::endl; } //Delete the values in order test_delete(6,B); test_delete(4,B); test_delete(1,B); test_delete(10,B); test_delete(8,B); test_delete(5,B); test_delete(12,B); //Implement this once you have //Everything else working run_experiment(); return 0; }

void test_insert(int v, BST* B) { insert(v,B); std::cout <<"Tree After Insert of " << v << std::endl; std::cout <<"Inorder:"<

//****Time to Run Your Experiment void run_experiment() { std::cout << "Experiments" << std::endl; std::cout << "| N | T1 | T2 | T3 | T4 | T5 | Average |"; std::cout << std::endl; int n=2; for(int i=1; i < 11; i++) { //Print the Row std::cout << "|" << std::left << std::setw(5) << std::setfill(' ') << n; //Run 5 Tests float avg=0; for(int j=0; j < 5; j++) { int res = single_experiment(n); std::cout << "|" << std::left << std::setw(6) << std::setfill(' ') << res; avg=avg+static_cast(res); } std::cout << "|" << std::left << std::setw(9) << std::setfill(' ') << (avg/5); //End std::cout << "|" << std::endl; n = n * 2; } }

//Have this function run 1 test //Generate a random tree with n elements //and return it's height //This function should insert n random numbers //into a BST. //Then return the height of the tree int single_experiment(int n) { //Generate n random integers //Insert into a new tree //return the height of the tree return 0; }

============================================

Example Output

 Tree After Insert of 6 Inorder: N 6 N Preorder: 6 N N Postorder: N N 6 Tree After Insert of 4 Inorder: N 4 N 6 N Preorder: 6 4 N N N Postorder: N N 4 N 6 Tree After Insert of 1 Inorder: N 1 N 4 N 6 N Preorder: 6 4 1 N N N N Postorder: N N 1 N 4 N 6 Tree After Insert of 10 Inorder: N 1 N 4 N 6 N 10 N Preorder: 6 4 1 N N N 10 N N Postorder: N N 1 N 4 N N 10 6 Tree After Insert of 8 Inorder: N 1 N 4 N 6 N 8 N 10 N Preorder: 6 4 1 N N N 10 8 N N N Postorder: N N 1 N 4 N N 8 N 10 6 Tree After Insert of 5 Inorder: N 1 N 4 N 5 N 6 N 8 N 10 N Preorder: 6 4 1 N N 5 N N 10 8 N N N Postorder: N N 1 N N 5 4 N N 8 N 10 6 Tree After Insert of 12 Inorder: N 1 N 4 N 5 N 6 N 8 N 10 N 12 N Preorder: 6 4 1 N N 5 N N 10 8 N N 12 N N Postorder: N N 1 N N 5 4 N N 8 N N 12 10 6 The Tree Height is 2 Is 0 in the tree? 0 Is 1 in the tree? 1 Is 2 in the tree? 0 Is 3 in the tree? 0 Is 4 in the tree? 1 Is 5 in the tree? 1 Is 6 in the tree? 1 Is 7 in the tree? 0 Is 8 in the tree? 1 Is 9 in the tree? 0 Is 10 in the tree? 1 Is 11 in the tree? 0 Is 12 in the tree? 1 Tree After Delete of 6 Inorder: N 1 N 4 N 5 N 8 N 10 N 12 N Preorder: 8 4 1 N N 5 N N 10 N 12 N N Postorder: N N 1 N N 5 4 N N N 12 10 8 Tree After Delete of 4 Inorder: N 1 N 5 N 8 N 10 N 12 N Preorder: 8 5 1 N N N 10 N 12 N N Postorder: N N 1 N 5 N N N 12 10 8 Tree After Delete of 1 Inorder: N 5 N 8 N 10 N 12 N Preorder: 8 5 N N 10 N 12 N N Postorder: N N 5 N N N 12 10 8 Tree After Delete of 10 Inorder: N 5 N 8 N 12 N Preorder: 8 5 N N 12 N N Postorder: N N 5 N N 12 8 Tree After Delete of 8 Inorder: N 5 N 12 N Preorder: 12 5 N N N Postorder: N N 5 N 12 Tree After Delete of 5 Inorder: N 12 N Preorder: 12 N N Postorder: N N 12 Tree After Delete of 12 Inorder: N Preorder: N Postorder: N

=====================================

Part 2

The main.cpp function is missing a function to test the average height of the BST. Complete this function. These results will be random, so don't expect to match the below exactly.

Example Output (only table shown)

 Experiments | N | T1 | T2 | T3 | T4 | T5 | Average | |2 |1 |1 |1 |1 |1 |1 | |4 |3 |2 |2 |2 |2 |2.2 | |8 |4 |5 |5 |3 |5 |4.4 | |16 |5 |5 |7 |6 |6 |5.8 | |32 |9 |10 |8 |8 |7 |8.4 | |64 |9 |10 |9 |14 |11 |10.6 | |128 |13 |13 |13 |13 |12 |12.8 | |256 |16 |17 |21 |15 |16 |17 | |512 |20 |16 |18 |21 |18 |18.6 | |1024 |22 |20 |21 |25 |22 |22 |