C++ Project - Binary Search Tree Problems, finding height, number of nodes and BST cloning
Binary Search Tree Implementation + Full DocumentationThis 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.
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