Write a C program to perform the following experiment: Generate 100 random numbe

Question

Write a C program to perform the following experiment: Generate 100 random numbers. As each number is generated, insert it into an initially empty binary search tree. When all 100 numbers have been inserted, print the level of the leaf with the largest level and the level of the leaf with the smallest level. Repeat this process 50 times. Print out a table with a count of how many of the 50 runs resulted in a difference between the maximum and minimum leaf level of 0, 1, 2, 3, and so on. Implement your binary tree using dynamically allocated nodes, not an array. Remember that each of your 50 repetitions needs to print the largest and smallest leaf levels. At the end of all 50 runs, your program will print a summary of level differences and the # of runs. Here an example of the output format:

Use the following function to generate a random int from 1 to 1000 for each node you insert into your binary search tree:

int generateRandom() {

return rand() % 1000 + 1;

}

You should initialize the random number generator with the following line in your main function: srand(time(NULL)); Note: to use the time() function, you need to include the header file at the top of your C source file.

Out Line:

Explanation / Answer

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
struct node
{
   int key;
   struct node *left, *right;
};

struct node *newNode(int item)
{
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp->key = item;
   temp->left = temp->right = NULL;
   return temp;
}

void inorder(struct node *root)
{
   if (root != NULL)
   {
       inorder(root->left);
       printf("%d ", root->key);
       inorder(root->right);
   }
}

struct node* insert(struct node* node, int key)
{

   if (node == NULL) return newNode(key);//empty
if (key < node->key)
       node->left = insert(node->left, key);
   else if (key > node->key)
       node->right = insert(node->right, key);
   return node;
}
int generateRandom()
{
return rand() % 100 + 1;
}

int main()
{
int number[100],i;
srand ( time(NULL) );
   struct node *root = NULL;
   for(i=0;i<100;i++)
   {
   number[i] = generateRandom();
   }
   for(i=0;i<100;i++)
   {
   root = insert(root, number[i]);
   insert(root, number[i+1]);
   }
   inorder(root);
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.