Please do this in C++ language Please do this in C++ language Please do this in
ID: 668274 • Letter: P
Question
Please do this in C++ language
Please do this in C++ language
Please do this in C++ language
Please do this in C++ language
1.Verify experimentally that the average depth of the nodes in randomly built binary search trees containing n nodes is O(log n)for trees containing n = 4, 32, 256, and 2048 nodes. Of course, it won’t be sufficient to generate just one randomly built binary search tree for each value of n. You’ll have to generate many trees for each value of n, calculate the average depth of the nodes for each tree generated, and then calculate the average depth of all the trees generated. For n = 4, 32, 256, and 2048, generate 8, 64, 512, and 4096 trees, respectively. Write the output that you generate into a comma-separated file and then import the file into an MS-Excel compatible spreadsheet. Compare the average depths on a graph, where n is on the x-axis and the average depth is on the y-axis. Hand-written graphs or graphs generated from manually entered data will not be accepted.
Do your work on one of the Linux machines in CL115. To log onto one of these machines, follow the instructions given above in Problem 1.
Submit to UR Courses: (1) the source code for your program, (2) a script file showing the compilation and execution of your program, and the contents of the average depth file (use the UNIX cat command to show the contents?), (3) the average depth file, and (4) the MS-Excel file containing the graph of the average depths.
If you are working alone, submit to UR Courses: (1) the source code for any .cpp and .h files you might have created (and only the .cpp and .h files) zipped into one file and (2) a single script file showing the execution of your program and the contents of the average depth file (use the UNIX cat command to show the contents of the average depth file in the script), (3) the average depth file, and (4) the MS-Excel compatible file containing the graph of the average depths.
If you are working in a partnership, one of the partners should submit to UR Courses: (1) a file named partners that provides the name and student numbers of the partners, (2) the source code for any .cpp and .h files you might have created (and only the .cpp and .h files) zipped into one file and (3) a single script file showing the execution of your program and the contents of the average depth file (use the UNIX cat command to show the contents of the running time file in the script), (4) the average depth file, and (5) the MS-Excel compatible file containing the graph of the average depths. The other partner/s should submit to UR Courses: (1) a file named partners that provides the name and student numbers of the partners. Note that all partners need to submit the partners file.
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
struct btnode
{
int value;
struct btnode *l;
struct btnode *r;
};
struct btnode *root;
typedef struct btnode bt;
bt *new,*ptr,*ptr1,*ptr2;
bt* create()
{
new = (bt *)malloc(sizeof(bt));
new->l = NULL;
new->r = NULL;
return new;
}
void construct_binary_tree()
{
root = create();
root->value = 50;
ptr = create();
root->l = ptr;
ptr->value = 20;
ptr1 = create();
ptr->l = ptr1;
ptr1->value = 70;
ptr2 = create();
ptr1->l = ptr2;
ptr2->value = 10;
ptr2 = create();
ptr1->r = ptr2;
ptr2->value = 40;
ptr1 = create();
ptr->r = ptr1;
ptr1->value = 80;
ptr2 = create();
ptr1->r = ptr2;
ptr2->value = 60;
ptr = create();
root->r = ptr;
ptr->value = 30;
}
void main()
{
int depth1 = 0, depth2 = 0;
construct_binary_tree();
ptr = root;
while (ptr->l != NULL || ptr->r != NULL)
{
depth1++;
if (ptr->l == NULL)
ptr = ptr->r;
else
ptr = ptr->l;
}
ptr = root;
while (ptr->l != NULL || ptr->r != NULL)
{
depth2++;
if (ptr->r == NULL)
ptr = ptr->l;
else
ptr = ptr->r;
}
/**DEPTH IS CONSIDERED FROM LEVEL-0 ALSO HEIGHT IS CONSIDERED AS NUMBER OF EDGES*/
if (depth1 > depth2)
printf("height of the tree is %d depth of the tree is %d",depth1,depth1);
else
printf("height of the tree is %d depth of the tree is %d",depth2,depth2);
}