Topics Step 1 :generate 50 random numbers ranging from 1 to 99 and store it in a
ID: 3813460 • Letter: T
Question
Topics
Step 1 :generate 50 random numbers ranging from 1 to 99 and store it in an array (DO NOT SORT THE ARRAY). Print these values to the screen.
Step 2: Now take one number at a time sequentially starting from the leftmost value (the value at index position 0 of the array) and insert it into a Binary Search Tree.
You can use a second array to store the Binary Search Tree - they must use the formula we discussed in class to store Left Child and Right Child.
Step 4: Upon building the Binary Search Tree, they must follow the rule that LeftChild < Parent <= RightChild.
Step 5: Print out the values of this second array.
Note: you must compare the original distribution of the values in the array vs the distribution after creating the Binary Search Tree (the second array/ArrayList) by printing this observation/comparison to the screen.
If a node has no left child or right child or both, the corresponding position of its left child or right child or both should be -1
the data type of each element in the array( used to store the BST) should be int
Index of the array is used to location the child.
Please use array for Binary Tree
Thanks!
Explanation / Answer
import java.util.Random;
class BinarySearchTree
{
public void accept(int A[],int n)
{
int i, randval;
Random rn = new Random();
for(i=0; i<n; i++)
{
randval = rn.nextInt(99)+1;
A[i]=randval;
}
}
public void create(int A[],int B[],int n,int max) //some logic need to be solved in this method
{
int i,j,k;
for(i=0;i<max;i++)
B[i]=-1;
B[0]=A[0];
j=0;
inner:
for(i=1;i<n;i++)
{
if(B[j]<A[i])
k=2*j+2;
else
k=2*j+1;
if(B[k]==-1)
{
B[k]=A[i];
j=0;
}
else
{
j=k;
break inner;
}
}//end of i loop
}
public void display(int X[],int n)
{
for(int i=0;i<n;i++)
System.out.print(X[i]+" ");
}
}
public class TestBST
{
private static int A[];
private static int B[];
public static void main(String args[])
{
A=new int[50];
B=new int[120];
BinarySearchTree bst=new BinarySearchTree();
bst.accept(A,50);
System.out.println(" Displaying Unsorted numbers Array:");
bst.display(A,50);
bst.create(A,B,50,120);
System.out.println(" Displaying Binary Search Tree numbers Array:");
bst.display(B,120);
}
}