Need help with this in c

Part 1: Finish BST Implementation(70 points)

You are provided with two files. There is data structure and function prototypes for a binary search three in bst.h. You are also given a test file in main.c for the BST. It has two possible tests. In this part of the assignment, you will only use option 1.

The program is missing the bst.c file. Your job it 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

 % ./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: 6 4 Inorder: 4 6 Postorder: 4 6 Inserted 1 into tree Preorder: 6 4 1 Inorder: 1 4 6 Postorder: 1 4 6 Inserted 10 into tree Preorder: 6 4 1 10 Inorder: 1 4 6 10 Postorder: 1 4 10 6 Inserted 8 into tree Preorder: 6 4 1 10 8 Inorder: 1 4 6 8 10 Postorder: 1 4 8 10 6 Inserted 5 into tree Preorder: 6 4 1 5 10 8 Inorder: 1 4 5 6 8 10 Postorder: 1 5 4 8 10 6 Inserted 12 into tree Preorder: 6 4 1 5 10 8 12 Inorder: 1 4 5 6 8 10 12 Postorder: 1 5 4 8 12 10 6 The Tree Height is 2 Is 0 in the tree? Answer: 0 Is 1 in the tree? Answer: 1 Is 2 in the tree? Answer: 0 Is 3 in the tree? Answer: 0 Is 4 in the tree? Answer: 1 Is 5 in the tree? Answer: 1 Is 6 in the tree? Answer: 1 Is 7 in the tree? Answer: 0 Is 8 in the tree? Answer: 1 Is 9 in the tree? Answer: 0 Is 10 in the tree? Answer: 1 Is 11 in the tree? Answer: 0 Is 12 in the tree? Answer: 1 Delete 6 from tree Preorder: 8 4 1 5 10 12 Inorder: 1 4 5 8 10 12 Postorder: 1 5 4 12 10 8 Delete 4 from tree Preorder: 8 5 1 10 12 Inorder: 1 5 8 10 12 Postorder: 1 5 12 10 8 Delete 1 from tree Preorder: 8 5 10 12 Inorder: 5 8 10 12 Postorder: 5 12 10 8 Delete 10 from tree Preorder: 8 5 12 Inorder: 5 8 12 Postorder: 5 12 8 Delete 8 from tree Preorder: 12 5 Inorder: 5 12 Postorder: 5 12 Delete 5 from tree Preorder: 12 Inorder: 12 Postorder: 12 Delete 12 from tree Preorder: Inorder: Postorder: 

Part 2: Average Heights (20 points)

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 is just luck. It should be formated as closely to the example as possible.

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 | | 2| 1| 1| 1| 1| 1| 1.00| | 4| 3| 3| 2| 3| 2| 2.60| | 8| 5| 4| 4| 4| 4| 4.20| | 16| 7| 6| 7| 7| 6| 6.60| | 32| 7| 8| 8| 8| 8| 7.80| | 64| 12| 12| 13| 11| 8| 11.20| | 128| 15| 13| 15| 13| 11| 13.40| | 256| 14| 15| 15| 15| 14| 14.60| | 512| 23| 22| 18| 17| 17| 19.40| | 1024| 22| 20| 19| 21| 25| 21.40| 

Part 3: Analysis (10 points)

In a file readme.md analyze your results. Generate 5 runs of the height experiment and put your results into this file. We know from class that the best case height is log2(n) and worst case is n. You are going to try to make a tighter estimate.

Come up with a formula that describes the heights you got in the random experiments. Try to get a reasonably tight range. You do not have to be perfect.

Something like:

2/3 n

log2(n)

7log2(n)

etc...

//---ONLY EDIT FUNCTION heightExperiments--- / /---Make no other changes-- \#include "bst.h" \#include "stdio.h" \#include "stdlib.h" \#include "time. h " Ask user for a list of numbers. Test BST with them. void inputTest( ) 1 Generate Random Trees and test heights. Print table of resuts. void heightExperiments (); Find Minimum in an Array eparam A is the array to search eparam size is the array size ereturn The minimum element in array int minV (int* A, int size); Find Maximum in an Array eparam A is the array to search Cparam size is the array size ereturn The max element in array int maxV( int* A1 int size); Read an integer from stdin. Consumes all characters till newline (ereturn Integer read int readNumber ( ) / * Test file for student BST code eparam argc not used eparam argv not used ereturn 0 on success and 1 on bad input 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. "); h bst > No Selection h bst h bst > No Selection