Need help with binary search tree in C++ code please

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:"< 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; }

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

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