Need help with binary search tree and completing C++ code please

Instruction: 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.

*please add/modify code to main.cpp code*

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 |

My current code below:

*please add function to main.cpp code below*

//main.cpp code

//Tests for Binary Search Tree

#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:"< inorder(B); std::cout <<"Preorder:"< preorder(B); std::cout <<"Postorder:"< postorder(B); } void test_delete(int v, BST* B) { delete_from_tree(v,B); std::cout <<"Tree After Delete of " << v << std::endl; std::cout <<"Inorder:"< inorder(B); std::cout <<"Preorder:"< preorder(B); std::cout <<"Postorder:"< postorder(B); }

//****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; } =======================================

//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 ========================================

//bst.cpp code below

#include "bst.h" #include using namespace std;

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) { if (current == NULL) return; inorder_walker(current->left); cout << current->value << " "; inorder_walker(current->right); return; } void preorder_walker(Node *current) { if (current == NULL) return; cout << current->value << " "; inorder_walker(current->left); inorder_walker(current->right); return; } void postorder_walker(Node *current) { if (current == NULL) return; inorder_walker(current->left); inorder_walker(current->right); cout << current->value << " "; return; }

Node *insert_value(int v, Node *current) { if (current == NULL) { Node *new_node = new Node; new_node->left = new_node->right = NULL; new_node->value = v; return new_node; }

if (v > current->value) { current->right = insert_value(v, current->right); } else { current->left = insert_value(v, current->left); }

return current; }

//Find value starting at current node bool find_value(int value, Node *current) { if (current == NULL) return false; if (current->value = value) return true;

return find_value(value, current->left) || find_value(value, current->right); }

//Find the min of the tree starting at current node //Return -1 on current is null int find_min(Node *current) { if (current == NULL) return -1; int a = current->value; int b = find_min(current->left); int c = find_min(current->right);

if (b == -1) b = INT32_MAX; if (c == -1) c = INT32_MAX; return min(a, min(b, c)); }

//Determine the node height of the current node //Hint: The height of a null is -1 int node_height(Node *current) { if (current == NULL) return -1; int a = 1; int b = node_height(current->left); int c = node_height(current->right);

if (b == -1) b = 0; if (c == -1) c = 0; return max(a + b, a + c); }

//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; }