The purpose of these programming problems is to gain experience using the array implementations of a binary tree.
Programming Problems (to be handed in):
Question 1: Use a random number generator to create 10 numbers between 1 and 1000 and store them in 2 different arrays. The first array should contain the numbers as they are generated. The second should store the same numbers in a tree implemented as acomputed link array using the strategy described below:
• The first element generated will be the root
• The rest of the elements will be stored in the left subtree if it is smaller than the root (or parent), otherwise it is stored in the right subtree.
• When entering the left subtree, the same strategy must be used to find the proper place in the left subtree (if new element is less than the parent, go into left subtree, otherwise go into right subtree).
• Continue this pattern until an empty spot is found in the array, and store the element there.
Ii is suggested to make your computed link array capable of holding at least 20 items, since there will be wasted space.
Once you’ve created the binary tree, then implement the inorder visit code from the lecture slides and conduct an inorder visit on the tree you created printing out each parent as you visit it. If you’ve set up the tree correctly, the output numbers should be sorted.
For this problem, output the original data, the data as stored in the computed link array (and draw lines on your output to show the children of each parent), and the output obtained from the inorder visit.
Question 2: The same as question 1, except that the stored link implementation is to be used to store the numbers as generated. In this case the array has only 10 storage areas (no wasted space, but be careful how you stop the search to find the correct spot).
DO NOT DO THE INORDER VISIT FOR THIS PROBLEM, JUST PRINT OUT THE DATA AS IT IS STORED IN THE STORED LINK ARRAY.
FOR BOTH PROBLEMS, DRAW A DIAGRAM OF THE FINAL VERSION OF THE TREE.