Binary Search Tree Implementation + Full Documentation
This programming assignment simulates the use and functionality of binary search trees (BST) by comparing statistics over several simulations.- Start the random number generator at the current time stamp -- similar or the same as srand(time(0)).
- Initialize variables to be used in the program’s final report.
- Define a struct node with four fields: node * left, * right; int data; and int frequency. Frequency means the number of times the specific data value was placed into the tree. So, instead of having a BST with the same data values, count the number of times (more than zero) that the data value was placed into the tree.
- Run the following 1000 times:
- Start with an empty binary search tree.
- Load 5000 integers with values between 0 and 1023 into the BST.
- Without changing that tree (Call it T1, here), create another empty BST, say T2 and load all the data from T1 into T2 in such a way that T2 is “balanced.”
- Gather the following three data items: Number of nodes in either tree (they will be the same). The average height of each tree.
- Make both trees empty.
- Write a report on the screen that explains the floating point averages of all the data items gathered in 4. d.
Note that collaboration is not permitted. If I feel you are using the code you don’t understand, I may question you about the code so that I can be convinced it is your work. Some of the techniques and functions here are similar to those used in class; some are substantially new. There will be plenty of time to ask questions in class to clarify.
Comments
Post a Comment