2 Create binary search tree BST that contains the first mill

2. Create binary search tree (BST) that contains the first million prime numbers. After you are reading in the data, output the maximum and average depth of the BST. Allow the user to enter a number to see whether or not it is prime. If the number is found, output the depth at which it was found. If the number isn\'t found, output the nearest prime number greater than and the nearest prime number less than the user\'s number.

Example output

Creating Binary Tree from 1000000 prime numbers...

The maximum depth of the tree is ?

The average depth of the tree is ?

Enter a number to see if it\'s in the tree:

25

Your number was not found.

The nearest prime number less than your number is 23

The nearest prime number greater than your number is 29

Solution

#include /*This is used to create a binary tree node has data, pointer to left child and a pointer to right child */ struct createnode { int data; struct createnode* left; struct createnode* right; }; /* This is used to compute the \"maxDepth\" of a tree which is equal to the number of nodes along the longest path from the root node down to the farthest leaf node.*/ int maximumDepth(struct createnode* node) { if (node==NULL) return 0; else { /* now we will compute the depth of each subtree */ int leftDepth = maxDepth(node->left); int rightDepth = maxDepth(node->right); /* the next step is to use the larger one */ if (leftDepth > rightDepth) return(leftDepth+1); else return(rightDepth+1); } } /* This is a helper function that allocates a new node with the given data and NULL left and right pointers. */ struct createnode* newNode(int data) { struct createnode* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return(node); } int main() { struct createnode *root = newNode(1); root->left = newNode(5); root->right = newNode(8); root->left->left = newNode(2); root->left->right = newNode(7); printf(\"The height of tree is %d\", maximumDepth(root)); getchar(); return 0; }