IN JAVA The aim is to allow students to learn about BST(Binary Search Tree) iii)
ID: 3576823 • Letter: I
Question
IN JAVA
The aim is to allow students to learn about BST(Binary Search Tree)
iii) Rewrite the program to print the content of the BST
import java.util.Scanner;
public class Binarysearch {
public static void main(String[] args) {
int c, first, last, middle, n, search, array[];
Scanner in = new Scanner(System.in);
System.out.println("Enter number of sorted elements in accending order");
n = in.nextInt();
array = new int[n];
System.out.println("Enter " + n + " integers");
for (c = 0; c < n; c++)
array[c] = in.nextInt();
System.out.println("Enter value to find");
search = in.nextInt();
first = 0;
last = n - 1;
middle = (first + last)/2;
while( first <= last )
{
if ( array[middle] < search )
first = middle + 1;
else if ( array[middle] == search )
{
System.out.println(search + " found at location " + (middle + 1) + ".");
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
if ( first > last )
System.out.println(search + " is not present in the list. ");
System.out.println("search="+search);
}
}
Explanation / Answer
Check first if root exists. If not, tree is empty, and, therefore, searched value doesn't exist in the tree. This check can be done in the BinarySearchTree class. Principal algorithm is implemented in the BSTNode class.
public class BinarySearchTree
{
public boolean search(int value)
{
if (root == null)
return false;
else
return root.search(value);
}
}
public class BSTNode
{
public boolean search(int value)
{
if (value == this.value)
return true;
else if (value < this.value)
{
if (left == null)
return false;
else
return left.search(value);
}
else if (value > this.value)
{
if (right == null)
return false;
else
return right.search(value);
}
return false;
}
}