PLS HELP IN JAVA: 1. This program buids a small BST of integers. Your mission is
ID: 3591978 • Letter: P
Question
PLS HELP IN JAVA: 1.This program buids a small BST of integers. Your mission is to write the method called Accesses that will return the number of accesses to find an element in the tree. The main program calls this method for each element, adding the accesses each time in order to count the total number of accesses. The program then outputs the total number of accesses and the average number.
2. Repeat the above for strings in an input file.
What I have:
public class BinaryTreeNode<T>
{
private T element;
private BinaryTreeNode<T> left, right;
/**
* Creates a new tree node with the specified data.
*
* @param obj the element that will become a part of the new tree node
*/
BinaryTreeNode (T obj)
{
element = obj;
left = null;
right = null;
}
public T getValue(){
return element;
}
public T getElement() {
return element;
}
public void setElement(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;
}
}
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
int totalAccesses=1; //# accesses to insert 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);
//count access to retrieve all data
for (int i = 1; i < arr.length; i++) {
//totalAccesses=totalAccesses+Accesses(root, arr[i]);
}
System.out.println("Number of accesses to find all data in tree is " + totalAccesses);
System.out.println("Average number of accesses is " + totalAccesses*1.0/arr.length);
}
//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 curr, Integer num)
{ BinaryTreeNode b=new BinaryTreeNode(num);
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();
}
}
}
}
public static void Accesses(){
}
}
Explanation / Answer
Access function :
public static int Accesses(BinaryTreeNode<Integer> root,int element){
//if root is null , return 0
if(root==null)
return 0;
//if element reached return 1
if(root.getElement()==element)
return 1;
//if element is less than current element then got to left and add 1 for current access
if(root.getElement()>element)
return 1+Accesses(root.left,element);
//if element is greater than current element then got to right and add 1 for current access
return 1+Accesses(root.right,element);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.