Question

write a method called Comparisons that will return the number of comparisons to find an element in the tree. The main program calls this method for each element, adding the comparisons each time in order to count the total number of comparisons. The program then outputs the total number of comparisons and the average number. You may use the program BuildTreeWIthMethod to build your tree. Then, after you have made the call to inOrder(root), add the following code:

int totalComparisons=0;

for (int i = 0; i < arr.length; i++) {

totalComparisons=totalComparisons + Comparisons(root, arr[i]);

}

System.out.println("Number of comparisons to find all data in tree is " + totalComparisons);

System.out.println("Average number of comparisons is " + totalComparisons*1.0/arr.length);

To be clear: you ONLY have to write the method and to put the code above into your program - use the program I gave to you.

2. Repeat the above for strings in an input file. The input file is here. words2.txt

In each case work the tree by hand (pencil and paper) so you know what the answer should be. You can EITHER submit two programs OR put both into one program. Your choice.

FOR THIS LAB it is OK if you have to write two TreeInsert methods (one for Integer, one for Strings), and two Comparisons methods (you can write template methods in the next lab) - but if you put template methods in here that is good too. ALSO the integers are in an array, but the Strings are in a file. So after you have built a tree of Strings you either have to close the input file, then reopen it and pick up each word again and calculate the number of comparisons to find it, or you have to look for another solution. (Possibilities are to read them into an array at the beginning before building your tree or count comparisons in the same loop where you read in your string. Either is fine (for now)).

words2.txt

Hi

Bye

Monday

April

Donkey

Yellow

Computers

Monkey

Dog

Cat

Answer 1

// BinaryTreeNode.java

public class BinaryTreeNode<T>
{
private T element;
private BinaryTreeNode<T> left, right;
  
  
BinaryTreeNode (T obj)
{
element = obj;
left = null;
right = null;
}
  
public T getValue(){
return element;
}
  
public void setValue(T element) {
this.element = element;
}
  
public BinaryTreeNode<T> getLeft() {
return left;
}
  
public void setLeft(BinaryTreeNode<T> left) {
this.left = left;
}
  
public BinaryTreeNode<T> getRight() {
return right;
}
  
public void setRight(BinaryTreeNode<T> right) {
this.right = right;
}

}

//end of BinaryTreeNode.java

// BuildTreeWithMethod.java

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class BuildTreeWithMethod {
  
public static void main(String[] args) throws FileNotFoundException {
  
System.out.println("Working with Integers: ");
Integer[] arr = {6, 8, 3, 4, 9, 2 }; //data to put in BST
  
BinaryTreeNode<Integer> root=new BinaryTreeNode<Integer>(arr[0]);//the root

//build the tree
for (int i = 1; i < arr.length; i++) {
  
TreeInsert(root, arr[i]);

}
//print out the data - should be sorted
inOrder(root);
  
int totalComparisons=0;

for (int i = 0; i < arr.length; i++) {
totalComparisons=totalComparisons + Comparisons(root, arr[i]);
}

System.out.println("Number of comparisons to find all data in tree is " + totalComparisons);
System.out.println("Average number of comparisons is " + totalComparisons*1.0/arr.length);
  
System.out.println("\nWorking with Strings: ");
String filename = "words2.txt";
// open file
Scanner fileScan = new Scanner(new File(filename));
String word;
  
// create root node and set it to null
BinaryTreeNode<String> rootStr = null;
  
// loop to read till the end of file word by word
while(fileScan.hasNext())
{
word = fileScan.next(); // read a word
  
// rootStr not set, initialize it with the word read
if(rootStr == null)
rootStr = new BinaryTreeNode<String>(word);
else // rootStr initialized, insert word in tree with root as rootStr
TreeInsert(rootStr, word);
}
  
fileScan.close(); // close the file

//print out the data - should be sorted
inOrder(rootStr);

// re-open the file to calculate total comparisons
fileScan = new Scanner(new File(filename));
totalComparisons=0;

int totalElements = 0;

// read till the end of file word by word, calculating total comparisons
while(fileScan.hasNext())
{
word = fileScan.next();

totalElements++;
totalComparisons=totalComparisons + Comparisons(rootStr, word);
  
}
  
fileScan.close(); // close the file

System.out.println("Number of comparisons to find all data in tree is " + totalComparisons);
System.out.println("Average number of comparisons is " + totalComparisons*1.0/totalElements);

  
}
  
//method to perform- an inorder traversal of a BST
public static void inOrder(BinaryTreeNode t) {
if (t != null)
{
inOrder(t.getLeft());
System.out.println(t.getValue());
inOrder(t.getRight());
}
}

//method to insert an integer (num) into a non-null BST tree
public static void TreeInsert(BinaryTreeNode root, Integer num)
{
BinaryTreeNode b=new BinaryTreeNode(num);
BinaryTreeNode curr=root;
while (curr != null) {
int currValue= (int)curr.getValue();
if(num<currValue){
if (curr.getLeft() == null) {
curr.setLeft(b);
  
break;
} else {
curr = curr.getLeft();
  
}
  
} else {
if (curr.getRight() == null) {
curr.setRight(b);
  
break;
} else {
curr = curr.getRight();
}
}
  
}
}
  
// method to return number of comparison to search for target
public static int Comparisons(BinaryTreeNode root, int target)
{
// set curr to root of tree
BinaryTreeNode curr = root;
int numComparison = 0; // initialize the numComparison to 0
  
// loop over the tree
while(curr != null)
{
// increment numComparison
numComparison++;
// get the current value
int currValue= (int)curr.getValue();
if(target == currValue) // target found, exit the loop
break;
else if(target > currValue) // target > currValue, search for target in right subtree
curr = curr.getRight();
else // target < currValue, search for target in left subtree
curr = curr.getLeft();
}
  
return numComparison;
}
  
//method to insert a string (str) into a non-null BST tree
public static void TreeInsert(BinaryTreeNode root, String str)
{
BinaryTreeNode b=new BinaryTreeNode(str);
BinaryTreeNode curr=root;
  
while (curr != null) {
String currValue= (String)curr.getValue();
  
if(str.compareTo(currValue) < 0){
if (curr.getLeft() == null) {
curr.setLeft(b);
break;
} else {
curr = curr.getLeft();
}
}
else {
if (curr.getRight() == null) {
curr.setRight(b);
  
break;
} else {
curr = curr.getRight();
}
}
}
}
  
// method to return number of comparison to search for target
public static int Comparisons(BinaryTreeNode root, String target)
{
// set curr to root of tree
BinaryTreeNode curr = root;
int numComparison = 0; // initialize numComparison to 0
  
// loop over the tree
while(curr != null)
{
numComparison++; // increment numComparison
// get the current value
String currValue= (String)curr.getValue();
  
if(target.equals(currValue)) // target found, exit the loop
break;
else if(target.compareTo(currValue) > 0) // target > currValue, search in right subtree
curr = curr.getRight();
else // target < currValue, search in left subtree
curr = curr.getLeft();
}
  
return numComparison;
}
}

// end of BuildTreeWithMethod.java

Output:

Input file: words2.txt

Output :

Feel free to contact me if you have any queries.

Thank you :)