data-structures - Struggling terribly on how to start and complete a file

Question

I am unsure how to complete these 3 methods. 4 Reference classes are also given (at the bottom)

I know I have to first start building the tree from the array "a" but I am not sure how to do that. SOS pls help. :(

---

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.

    public static Queue<BTNode<dataNode>> 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<BTNode<dataNode>> join(Queue<BTNode<dataNode>> 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<dataNode> 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 class dataNode implements Comparable<dataNode>{
    public double value;
    public int count;
    public double max;
    public double min;
    
    public dataNode() {
        value=0;
        count=0;
    }
    
    public int compareTo(dataNode node2) {
        return 0;
    }
    
    public String toString() {
        return "("+value+","+count+")";
    }

}
---------
public class BTNode<T extends Comparable<T>> {
    private T data;
    private BTNode<T> left,right,parent;
    
    public BTNode(T data,BTNode<T> left,BTNode<T> right,BTNode<T> parent) {
        this.data=data;
        this.left=left;
        this.right=right;
        this.parent=parent;
    }
    
    public BTNode<T> getLeft(){
        return this.left;
    }
    
    public BTNode<T> getRight(){
        return this.right;
    }

    public BTNode<T> getParent(){
        return this.parent;
    }
    
    public T getData(){
        return this.data;
    }
    
    public void setLeft(BTNode<T> left) {
        this.left=left;
    }

    public void setRight(BTNode<T> right) {
        this.right=right;
    }

    public void setParent(BTNode<T> parent) {
        this.parent=parent;
    }
    
    public void setData(T data) {
        this.data=data;
    }

    public String toString() {
        return this.data.toString();
    }
}
----------
public class DLL<T> {
    private Node<T> first;
    private Node<T> last;
    private int count;
    private Node<T> current;

    public DLL() {
        this.first=null;
        this.last=null;
        count=0;
    }
    
    public T getFirst() {
        current=first;
        if (first!=null)
            return first.getData();
        return null;
    }
    
    public T getNext() {
        if (current!=null) {
            current=current.getNext();
            return current.getData();
        }
        return null;
    }
    
    public T getLast() {
        if (last!=null)
            return last.getData();
        return null;
    }
    
    public void addFirst(T data) {
        Node<T> n=new Node<T>(data,null,first);
        if (this.first!=null) {
            this.first.setPrev(n);
        }
        else {
            this.last=n;
        }
        this.first=n;
        count++;
    }
    
    public void addLast(T data) {
        Node<T> n=new Node<T>(data,last,null);
        if (this.last!=null) {
            this.last.setNext(n);
        }
        else {
            this.first=n;
        }
        this.last=n;
        count++;
    }

    public void deleteFirst() {
        if (this.first!=null) {
            Node<T> newFirst=this.first.getNext();
            this.first=newFirst;
            if (newFirst!=null) {
                newFirst.setPrev(null);
            }
            else {
                this.last=null;
            }
            count--;
        }
    }

    public void deleteLast() {
        if (this.last!=null) {
            Node<T> newLast=this.last.getPrev();
            this.last=newLast;
            if (newLast!=null) {
                newLast.setNext(null);
            }
            else {
                this.first=null;
            }
            count--;
        }
    }


    public void traverse() {
        Node<T> current=this.first;
        while (current!=null) {
            System.out.print(current.getData()+" ");
            current=current.getNext();
        }
    }

    
    public int size() {
        return count;
    }
    
    public String toString() {
        String ret="";
        Node<T> current=this.first;
        while (current!=null) {
            ret=ret+"+"+current.getData();
            current=current.getNext();
        }
        return ret;
    }
    
}
------------
public class Node<T> {
    private T data;
    private Node<T> prev;
    private Node<T> next;
    
    public Node(T data,Node<T> prev,Node<T> next) {
        this.data=data;
        this.prev=prev;
        this.next=next;
    }
    
    public T getData() {
        return data;
    }
    
    public Node<T> getPrev(){
        return prev;
    }
    
    public Node<T> getNext(){
        return next;
    }
    
    public void setPrev(Node<T> prev) {
        this.prev=prev;
    }
    
    public void setNext(Node<T> next) {
        this.next=next;
    }
}
-----------
public class Queue<T> {
    private DLL<T> myList;
    
    public Queue() {
        myList=new DLL<T>();
    }
    
    public void enqueue(T element) {
        myList.addFirst(element);
    }
    
    public T dequeue() {
        T element=null;
        if (myList.size()>0) {
            element = myList.getLast();
            myList.deleteLast();
        }
        return element;
    }
    
    public int size() {
        return myList.size();
    }
    
    public boolean isEmpty() {
        return myList.size()==0;
    }
    
    public void traverse() {
        myList.traverse();
    }

    public static void main(String[] args) {
        Queue<String> myQueue=new Queue<String>();
        
        myQueue.enqueue("the");
        myQueue.enqueue("quick");
        myQueue.enqueue("brown");
        myQueue.enqueue("fox");
        myQueue.enqueue("jumps");
        myQueue.enqueue("over");
        
        myQueue.traverse();
        
        System.out.println("dequeue->"+myQueue.dequeue());
        
        myQueue.traverse();
        myQueue.enqueue("the");
        myQueue.enqueue("lazy");
        myQueue.traverse();     
        
        System.out.println("dequeue->"+myQueue.dequeue());
        
        myQueue.traverse();     
    }
    
}

标签： data-structuresqueuebinary-search-treenodesdoubly-linked-list