Question

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.

Answer 1

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.