Question

In JAVA!!!

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 comparisonsto 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

BuildTreeWithMethod

public class BuildTreeWithMethod {

public static void main(String[] args) {
  
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);

}
//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();

}
}
}
  

}
  
}

Answer 1

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


public class BuildTreeWithMethod {

        public static void main(String[] args) throws FileNotFoundException {

                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);

                List<String> s = new ArrayList<>(); //String arraylist

                //Scanning input from file
                File file = new File("words2.txt"); //Enter the file location
                Scanner sc = new Scanner(file); 
                while (sc.hasNextLine()) 
                        s.add(sc.nextLine());

                BinaryTreeNode<String> p = new BinaryTreeNode<String>(s.get(0));
                //String Binary Tree Node

                for (int i = 1; i < s.size(); i++) {
                        TreeInsert(p, s.get(i));
                }

                totalComparisons = 0;

                for (int i = 0; i < s.size(); i++) {
                        totalComparisons=totalComparisons + Comparisons(p, s.get(i));
                        //System.out.println(totalComparisons);
                }

                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/s.size());

        }

        //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());

                }
        }

        //Comparison method for Integer
        public static int Comparisons(BinaryTreeNode<Integer> root, int toFind)
        {       
                int count=1;
                BinaryTreeNode<Integer> node=root;

                //check whether the value of node is equal to toFind
                while(!(node.getValue().intValue()==toFind))
                {
                        if(node.getValue().intValue()>toFind) {
                                node = node.getLeft();
                                count++;
                        }
                        else {
                                node = node.getRight();
                                count++;
                        }
                }
                return count;
        }

        //Comparison method for String
        public static int Comparisons(BinaryTreeNode<String> root, String toFind)
        {       
                int count=1;
                BinaryTreeNode<String> node=root;

                //check whether the value of node is equal to toFind
                while(!node.getValue().equals(toFind))
                {
                        if(node.getValue().compareTo(toFind)>0) {
                                node = node.getLeft();
                                count++;
                        }
                        else {
                                node = node.getRight();
                                count++;
                        }
                }
                return count;
        }



        //method to insert an integer (num) into a non-null BST tree
        public static void TreeInsert(BinaryTreeNode<Integer> 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 insert an String into a non-null BST tree
        public static void TreeInsert(BinaryTreeNode<String> root, String num)
        { 
                BinaryTreeNode<String> b= new BinaryTreeNode(num);
                BinaryTreeNode<String> curr=root;
                while (curr != null) {
                        String currValue = curr.getValue();
                        if(num.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();
                                }
                        }
                }
        }
}

output: