Question

In: Computer Science

public class Assignment3 { public static Queue> makeQueue(double[] a){ // Each element of the given array...

public class Assignment3 {

public static Queue> makeQueue(double[] a){

// Each element of the given array a must be inserted into a BTNode,

// this method returns a queue of BTNodes, each node will contain a dataNode

// the dataNode will have the value equal to the element of the array

// count equal to the number of times that the element repeats // min and max must be equal to value.

// the BTNode created must have its parent, right, and left references set to null

return null;

}

public static Queue> join(Queue> myQueue){

// For every two elements dequeued from myQueue create a new root element and

// make the two dequeued elements be the left and right child of that root.

// Each new root must contain the min value, obtained from the left subtree,

// the max value, obtained from the right subtree, and the value should be

// equal to the average of the maximum value of the left subtree and the

// minimum value of the right subtree, count should be set equal to 0 (internal node)

// Enqueue each new root node into another queue and return that queue.

// In case that only one element is left in myQueue, just enqueue it

// in the queue that will be returned.

return null;

}

public static int search(BTNode root,double target) {

// given a target value recursively search on the left or the right subtrees

// by comparing the value in root to the target. You know that you got to a

// leaf when the value count of the root is not equal to 0.

return 0;

}

public static void main(String[] args) {

// this is given to you and should work with your methods.

// The expected output is:

// (13.0,1) (12.5,1) (12.3,1) (12.1,1) (11.9,1) (10.3,2) (10.0,1) (9.2,1) (9.1,1) (8.0,1) (7.2,3) (5.8,2) (2.3,1) (1.0,1)

// (10.15,0) 7.2 0

// (7.6,0) 7.2 0

// (4.05,0) 7.2 0

// (6.5,0) 7.2 0

// (7.2,3) 7.2 3

// 3 double[] a = {1,2.3,5.8,5.8,7.2,7.2,7.2,8,9.1,9.2,10,10.3,10.3,11.9,12.1,12.3,12.5,13};

Queue> myQueue=makeQueue(a);

myQueue.traverse();

System.out.println();

while (myQueue.size()>1) {

myQueue=join(myQueue);

}

BTNode root=myQueue.dequeue();

System.out.println(search(root,7.2));

}

}

Binary Tree The data stored in the binary tree are doubles. The binary tree will store the data only on the leaves. The internal nodes are used for searching only. Your tree will work like a normal BST, to find a target element, your program will compare it to the root of the current subtree and if the target is less than the value of the root you will recursively search on the left subtree, otherwise, you will search on the right subtree. Your tree will allow duplicate values, by keeping track of the number of times that a particular value appears (this data is kept only in the leaves). Your binary tree is always created from scratch given a sorted array of doubles, in such a way that the root of every subtree (not a leaf) contains the average of the maximum element in the left subtree and the minimum element in the right subtree.

Example: Suppose that you are given the following array: 1, 2.3, 5.8, 5.8, 7.2, 7.2, 7.2, 8, 9.1, 9.2, 10, 10.3, 10.3, 11.9, 12.1, 12.3, 12.5, 13

The tree that is generated has a root with a value of 10.15, which is the average of the maximum value of the left subtree (which is 10) and the minimum value of the right subtree (which is 10.3), so the root has a value of (10+10.3)/2 = 10.15 The leaves have the actual values and the number of times each value appears.

Solutions

Expert Solution

public class Assignment3 {

    public static Queue<BTNode<dataNode>> makeQueue(double[] a) {

        Queue<BTNode<dataNode>> result = new Queue<>();
        
        dataNode lastnode = null;
        
        for(double x: a) {
            if(lastnode != null && lastnode.value == x) {
                lastnode.count += 1;
            } else {
                lastnode = new dataNode();
                lastnode.count = 1;
                lastnode.value = x;
                lastnode.min = x;
                lastnode.max = x;
                
                result.enqueue(new BTNode<>(lastnode, null, null, null));
            }
        }
        
        return result;

    }

    public static Queue<BTNode<dataNode>> join(Queue<BTNode<dataNode>> myQueue) {

        Queue<BTNode<dataNode>> result = new Queue<>();
        
        while(!myQueue.isEmpty()) {
            
            if(myQueue.size() > 1) {
                BTNode<dataNode> x = myQueue.dequeue();
                BTNode<dataNode> y = myQueue.dequeue();
                
                double val = (x.getData().max + y.getData().min) / 2.0;
                dataNode rootNode = new dataNode();
                rootNode.value = val;
                rootNode.max = y.getData().max;
                rootNode.min = x.getData().min;
                rootNode.count = 0;
                
                BTNode<dataNode> root = new BTNode<dataNode>(rootNode, x, y, null);
                x.setParent(root);
                y.setParent(root);
                result.enqueue(root);
            } else {
                result.enqueue(myQueue.dequeue());
            }
            
        }
        
        return result;

    }

    public static int search(BTNode<dataNode> root, double target) {
        System.out.println(root + " " + target + " " + root.getData().count);
        if(root != null && root.getData().count == 0) {
            if(root.getData().value > target) {
                return search(root.getLeft(), target);
            }
            else {
                return search(root.getRight(), target);
            }
        }
        
        if(root != null && root.getData().value == target) {
            return root.getData().count;
        }

        return 0;
    }

    public static void main(String[] args) {

        double[] a = { 1, 2.3, 5.8, 5.8, 7.2, 7.2, 7.2, 8, 9.1, 9.2, 10, 10.3, 10.3, 11.9, 12.1, 12.3, 12.5, 13 };

        Queue<BTNode<dataNode>> myQueue = makeQueue(a);
        myQueue.traverse();
        System.out.println();

        while (myQueue.size() > 1) {
            myQueue = join(myQueue);
        }

        BTNode<dataNode> root = myQueue.dequeue();
        System.out.println(search(root, 7.2));

    }

}

**************************************************

Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.

Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.


Related Solutions

public class MyLinked {    static class Node {        public Node (double item, Node...
public class MyLinked {    static class Node {        public Node (double item, Node next) { this.item = item; this.next = next; }        public double item;        public Node next;    }    int N;    Node first;     // remove all occurrences of item from the list    public void remove (double item) {        // TODO    } Write the remove function. Do NOT add any fields to the node/list classes, do...
import java.util.Random; class Conversions { public static void main(String[] args) { public static double quartsToGallons(double quarts)...
import java.util.Random; class Conversions { public static void main(String[] args) { public static double quartsToGallons(double quarts) { return quarts * 0.25; } public static double milesToFeet(double miles) { return miles * 5280; } public static double milesToInches(double miles) { return miles * 63360; } public static double milesToYards(double miles) { return miles * 1760; } public static double milesToMeters(double miles) { return miles * 1609.34; } public static double milesToKilometer(double miles) { return milesToMeters(miles) / 1000.0; } public static double...
import java.util.Scanner; public class Lab9Q3 { public static void main (String [] atgs) { double mass;...
import java.util.Scanner; public class Lab9Q3 { public static void main (String [] atgs) { double mass; double velocity; double totalkineticEnergy;    Scanner keyboard = new Scanner (System.in); System.out.println ("Please enter the objects mass in kilograms"); mass = keyboard.nextDouble();    System.out.println ("Please enter the objects velocity in meters per second: "); velocity = keyboard.nextDouble();    double actualTotal = kineticEnergy (mass, velocity); System.out.println ("Objects Kinetic Energy: " + actualTotal); } public static double kineticEnergy (double mass, double velocity) { double totalkineticEnergy =...
public class Lab1 { public static void main(String[] args) { int array [] = {10, 20,...
public class Lab1 { public static void main(String[] args) { int array [] = {10, 20, 31, 40, 55, 60, 65525}; System.out.println(findPattern(array)); } private static int findPattern(int[] arr) { for (int i = 0; i < arr.length - 2; i++) { int sum = 0; for (int j = i; j < i + 2; j++) { sum += Math.abs(arr[j] - arr[j + 1]); } if (sum == 20) return i; } return -1; } } QUESTION: Modify the given...
Define empty methods in Queue class using LinkedList class in Java ------------------------------------------------------------------------------- //Queue class public class...
Define empty methods in Queue class using LinkedList class in Java ------------------------------------------------------------------------------- //Queue class public class Queue{ public Queue(){ // use the linked list } public void enqueue(int item){ // add item to end of queue } public int dequeue(){ // remove & return item from the front of the queue } public int peek(){ // return item from front of queue without removing it } public boolean isEmpty(){ // return true if the Queue is empty, otherwise false }...
class Main { public static void main(String[] args) {        int[] array = {1,2,3,4,5};   ...
class Main { public static void main(String[] args) {        int[] array = {1,2,3,4,5};        //Complexity Analysis //Instructions: Print the time complexity of method Q1_3 with respect to n=Size of input array. For example, if the complexity of the //algorithm is Big O nlogn, add the following code where specified: System.out.println("O(nlogn)"); //TODO }    public static void Q1_3(int[] array){ int count = 0; for(int i = 0; i < array.length; i++){ for(int j = i; j < array.length;...
public class sales_receipt { public static void main(String[] args) { //declare varables final double tax_rate =...
public class sales_receipt { public static void main(String[] args) { //declare varables final double tax_rate = 0.05; //tax rate String cashier_name = "xxx"; //sales person String article1, article2; //item name for each purchased int quantity1, quantity2; //number of quantities for each item double unit_cost1, unit_cost2; //unit price for each item double price1, price2; //calculates amounts of money for each item. double sub_total; //total price of two items without tax double tax; //amount of sales tax double total; //total price of...
A incomplete definition of a class Temperature is given below: public class Temperature { private double...
A incomplete definition of a class Temperature is given below: public class Temperature { private double value[] = {36.5, 40, 37, 38.3}; } [6] (i) Copy and put it in a new class. Write a method toString() of the class, which does not have any parameters and returns a string containing all the values separated by newlines. When the string is printed, each value should appear on a line in the ascending order of their indexes. Copy the content of...
public class ArraySkills { public static void main(String[] args) { // *********************** // For each item...
public class ArraySkills { public static void main(String[] args) { // *********************** // For each item below you must code the solution. You may not use any of the // methods found in the Arrays class or the Collections classes // You must use Java's built-in Arrays. You are welcome to use the Math and/or Random class if necessary. // You MUST put your code directly beneath the comment for each item indicated. String[] myData; // 1. Instantiate the given...
Given an array of integers, delete each element from the array which is a multiple of 5, and display the rest of the array.
Given an array of integers, delete each element from the array which is a multiple of 5, and display the rest of the array.Input:    6    2 3 4 11 22 320    where:First line represents the number of elements in the array.Second line represents the elements in the array.Output:    2 3 4 11 22Explanation: Element of the array 320 is the only one in the array which is a multiple of 5, so it is removed from the array.Assumptions:Array can be of size...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT