The program should be in java Create binary search tree (BST) that contains the
ID: 3699111 • Letter: T
Question
The program should be in java
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 ?
import java.util.*;
import java.io.*;
public class tree
{
public static void main (String [] args) throws IOException
{
int userChoice;
Scanner input = new Scanner(System.in);
/*********************************************************/
File file = new File("primes4.txt");
Scanner infile = new Scanner(file);
int Count = 1;
Int MaxDepth = 0;
Temp = new Node();
Root.Data = infile.nextInt();
while (infile.hasNextInt())
{
Count++;
Depth = 0;
insert(Root, infile.nextInt());
if(Depth > MaxDepth)
MaxDepth = Depth;
}
System.out.println("Finished reading " + Count + " Prime numbers ");
System.out.println("Maximum Depth = " + MaxDepth);
} // end main
static void Insert(Node TheNode, int TheData)
{
if (TheNode.Data > NewData && TheNode.Right == null)
{
Node T = new Node();
T.Data = NewData;
TheNode.Left = T;
}
else if (TheNode.Data < NewData && TheNode.Right == null)
{
Node T = new Node();
T.Data = NewData;
TheNode.Right = T;
}
else if (TheNode.Data > TheData && TheNode.Left == null)
Insert(TheNode.Left, NewData);
else if (TheNode.Data < TheData && TheNode.Right == null)
Insert(TheNode.Right, NewData);
}
}
class Node
{
int Data;
Node Next;
}
Explanation / Answer
SourceCode:
import java.util.Scanner;
public class BinaryTree {
public static void main(String[] args) {
new BinaryTree().run();
}
static class Node {
Node left;
Node right;
int value;
public Node(int value) {
this.value = value;
}
}
public void run() {
int count=0;
Node root = new Node(2);
System.out.println("Building the tree having root value " + root.value);
for(int i=3;count<100;i++){
if(isPrime(i)==true){
count+=1;
insert(root,i);
}
}
System.out.println("Traversing the tree in order");
printTreeInOrder(root);
Scanner s=new Scanner(System.in);
System.out.println("Enter a number to check if it is prime or not: ");
int num=s.nextInt();
if(isPrime(num)==true){
System.out.println(num+" is Prime number");
}else{
for(int i=2;i<num;i++){
if(isPrime(i)==true){
System.out.println("Nearest prime number lesser than "+num+" is "+i);
break;
}
}
for(int i=num+1;;i++){
if(isPrime(i)==true){
System.out.println("Nearest prime number greater than "+num+" is "+i);
break;
}
}
}
}
public void insert(Node node,int value) {
if (value<node.value) {
if (node.left!=null) {
insert(node.left,value);
} else {
System.out.println("Inserted " + value + " to the left of "+ node.value);
node.left=new Node(value);
}
} else if (value >node.value) {
if (node.right!=null) {
insert(node.right,value);
} else {
System.out.println("Inserted " + value + " to the right of "+ node.value);
node.right=new Node(value);
}
}
}
public void printTreeInOrder(Node node) {
if (node!=null) {
printTreeInOrder(node.left);
System.out.println(node.value);
printTreeInOrder(node.right);
}
}
public boolean isPrime(int n){
for(int i=2;i<=n/2;i++){
if(n%i==0){
return false;
}
}
return true;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.