Main.c is provided:

#include "bst.h" #include "stdio.h" #include "stdlib.h" #include "time.h" void inputTest();

void heightExperiments(); int minV(int *A, int size); int maxV(int *A, int size); int readNumber(); int main(int argc, char **argv) { // Set random number generator srand(time(NULL)); // Users has two options printf("Select Option: "); printf("1.) Enter Tree Values and print tree. "); printf("2.) Run Height Experiments. "); // Read the users answer int r = readNumber(); if (r 2) { printf("Bad Input. Try Again. "); return 1; } if (r == 1) { inputTest(); return 0; } if (r == 2) { heightExperiments(); return 0; } return 0; }

// Get an array of numbers from user. // Insert, Find and Delete All of them. void inputTest() { // Ask for Size (assume good input) printf("Enter Number of Values to Test: "); int testSize = readNumber(); // read values int *A = malloc(sizeof(int) * testSize); for (int i = 0; i

// Clear Memory deleteBST(B); return; }

int minV(int *A, int size) { int myMin = 9999; for (int i = 0; i myMax) { myMax = A[i]; } } return myMax; }

// Read a number from STDIN int readNumber() { int number = 0; char c = getchar(); while (c != ' ') { number = number * 10 + (c - 48); c = getchar(); } return number; }

// Students must implement this function void heightExperiments() { printf("Implement Me! "); } bst.h is given:

#ifndef _BST_H_ #define _BST_H_

/** A structure to represent a single node in a binary search tree. */ struct Node { int value; /**

/** A structure to represent a binary search tree. */ struct BST { Node *root; /**

/** Create a new empty Binary Search Tree @return Pointer to empty BST */ BST *newBST(); /** Free all the memory allocated to the BST @param T is the tree to delete from memory */ void deleteBST(BST *T); /** Insert a value into the BST. Ignore duplicates. @param T is the tree to insert into @param target is the value to insert */ void insert(BST *T, int target); /** Find a value in the BST. @param T is the tree to search @param target is the value to search for @return 1 if found and 0 if not in tree */ char find(BST *T, int target); /** Delete a value from the tree @param T is the tree to delete from @param target is the value to delete */ void deleteFromTree(BST *T, int target); /** Find the Minimum in the BST. @param T is the tree to search for the min @return The smallest number in the tree */ int min(BST *T); /** Print the tree in inorder to stdout. End with newline @param T is the tree to print */ void inorder(BST *T); /** Print the tree in preorder to stdout. End with newline @param T is the tree to print */ void preorder(BST *T); /** Print the tree in postorder to stdout. End with newline @param T is the tree to print */ void postorder(BST *T); /** Find the height of the tree. @param T is tree to check the height on @param The number of edges in longest path to root. -1 for null tree. */ int height(BST *T);

// These methods act on Nodes // They can be implemented recursively. /** Recursively print the tree inorder. End with a space. @param current is the node to print */ void inorderWalker(Node *current); /** Recursively print the tree preorder. End with a space. @param current is the node to print */ void preorderWalker(Node *current); /** Recursively print the tree postorder. End with a space @param current is the node to print */ void postorderWalker(Node *current); /** Insert a value starting at a node recursively. @param target is the value to insert @param current is the node to start at @return Updated pointer to node after changes */ Node *insertValue(int target, Node *current); /** Find a value in the tree starting at node recursively. @param target is the value to search for @param current is the node to start at @return 1 if found and 0 if not found */ char findValue(int target, Node *current); /** Find the minimum value starting at node recursively @param current is the node to start looking at @return The minimum of the section of the three starting at current */ int findMin(Node *current); /** Find the height of a node. Null has height -1. @param current is the node to find the height of @return The height of the node in question */ int nodeHeight(Node *current); /* Delete a value from the BST starting at node recursively. @param target is the value to delete @param current is the node to start at @return The updated node pointer */ Node *deleteValue(int target, Node *current); /** Delete a specific node. @param current is the node to delete @return Updated pointer to replace node in the tree */ Node *deleteNode(Node *current);

#endif Part 1:

There is data structure and function prototypes for a binary search three in bst.h. Also given a test file in main.c for the BST. It has two possible tests. In part 1 of the assignment, you will only use option 1. The program is missing the bst.c file. We need to create this file and implement everything described in bst.h. When running the program you will be asked which option to select. For this part select 1. Then you can enter numbers and a BST will be made with those numbers. Example output:

Part 2:

The main.c program is missing a function to test the average height of the BST. Complete this function. The random number generator has already been seeded.This function should generate 5 random binary search trees for each number of element n. Then print out the height of the each tree.Finish the program so that it will generate the table. Since the values are random, your heights will not be exactly the same as the output. It should be formated as closely to the example as possible. Example output:

Example Output %./ main Select Option: 1.) Enter Tree Values and print tree. 2.) Run Height Experiments. 1 Enter Number of Values to Test: 7 Enter A[0] value: 6 Enter A[1] value: 4 Enter A[2] value: 1 Enter A[3] value: 10 Enter A[4] value: 8 Enter A[5] value: 5 Enter A[6] value: 12 Inserted 6 into tree Preorder: 6 Inorder: 6 Postorder: 6 Inserted 4 into tree Preorder: 64 Inorder: 46 Postorder: 46 Inserted 1 into tree Preorder: 641 Inorder: 146 Postorder: 146 Inserted 10 into tree Preorder: 64110 Inorder: 14610 Postorder: 14106 Inserted 8 into tree Preorder: 641108 Inorder: 146810 Example Output %./ main Select Option: 1.) Enter Tree Values and print tree. 2.) Run Height Experiments. 2 Experiments ( N= Number Element, Table Shows Height) N|T1|T2|T3|T4|T5|Average|2481632641282565121024135771215142322134681213152220124781315151819134781113151721124688111417251.002.604.206.607.8011.2013.4014.6019.4021.40