Я не уверен, как использовать эти 3 метода. Также даны 4 ссылочных класса (внизу)
Я знаю, что мне нужно сначала начать построение дерева из массива «a», но я не уверен, как это сделать. SOS, пожалуйста, помогите. : (
Данные, хранящиеся в двоичном дереве, являются двойными. Бинарное дерево будет хранить данные только на листьях. Внутренние узлы используются только для поиска.
Ваше дерево будет работать как обычный BST, чтобы найти целевой элемент, ваша программа сравнит его с root текущего поддерева, и если цель меньше чем значение root, вы будете рекурсивно искать в левом поддереве. В противном случае вы будете искать в правом поддереве.
Ваше дерево допускает повторяющиеся значения, отслеживая, сколько раз появляется конкретное значение (эти данные хранятся только в листьях).
Ваше двоичное дерево всегда создается с нуля с учетом отсортированного массива двойников таким образом, что root каждого поддерева (не лист) содержит среднее значение максимального элемента в левом поддереве и минимального элемента в правом поддереве. Пример:
Предположим, вам дан следующий массив: 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
Сгенерированное дерево имеет root со значением 10,15, которое является средним из максимального значения левого поддерева (которое равно 10) и минимального значения правого поддерева ( что равно 10,3), поэтому root имеет значение (10 + 10,3) / 2 = 10,15
Листы имеют фактические значения и количество раз, когда каждое значение появляется.
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();
}
}