On AVLTree.java, implement:

? rotateLeft ? rotateLeftRight ? getHeightDifference ? Should return the difference in height between the subtrees of the incoming node. A positive # if the left subtree is taller, negative # otherwise. Run the driver program, and the output should be: 60, 40, 80, 20, 50, 70, 90, 10, 35, 55

QueuePackage (LinkedQueue and QueueInterface)

LinkedQueue

package QueuePackage; import java.util.EmptyStackException; public class LinkedQueue implements QueueInterface { private int numEntries = 0; private Node firstNode; private Node lastNode; public LinkedQueue() { firstNode = null; lastNode = null; } private class Node { private T data; private Node next; private Node(T d, Node n) { next = n; data = d; } public void setNextNode(Node n) { next = n; } public T getData(){ return data; } public void setData(T d) { data = d; } public Node getNextNode() { return next; } } @Override public void enqueue(T newEntry) { Node newNode = new Node(newEntry, null); if(isEmpty()) { firstNode = newNode; } else { lastNode.setNextNode(newNode); } lastNode = newNode; numEntries++; } @Override public T dequeue() { T front = getFront(); if(front == null) { throw new EmptyStackException(); } firstNode.setData(null); firstNode = firstNode.getNextNode(); if(firstNode == null) { lastNode = null; } numEntries--; return front; } @Override public T getFront() { if(isEmpty()) { throw new EmptyStackException(); } else { return firstNode.getData(); } } public T getBack() { return lastNode.getData(); } @Override public boolean isEmpty() { return (firstNode == null) && (lastNode == null); } @Override public void clear() { firstNode = null; lastNode = null; } public int getNumEntries() { return numEntries; } }

QueueInterface

package QueuePackage; public interface QueueInterface { public void enqueue(T newEntry); public T dequeue(); public T getFront(); public boolean isEmpty(); public void clear(); } 

StackPackage(ArrayStack and StackInterface)

ArrayStack

package StackPackage; import java.util.Arrays; import java.util.EmptyStackException; public class ArrayStack implements StackInterface { private T[] stack; private int topIndex; // index of top entry private static final int DEFAULT_CAPACITY = 50; private static final int MAX_CAPACITY = 10000; public ArrayStack() { this(DEFAULT_CAPACITY); } public ArrayStack(int initialCapacity) { checkCapacity(initialCapacity); @SuppressWarnings("unchecked") T[] tempStack = (T[])new Object[initialCapacity]; stack = tempStack; topIndex = -1; } @Override public T pop() { if(isEmpty()) { throw new EmptyStackException(); } else { T top = stack[topIndex]; stack[topIndex] = null; topIndex--; return top; } } @Override public void push(T newEntry) { ensureCapacity(); stack[topIndex + 1] = newEntry; topIndex ++; } @Override public T peek() { if(isEmpty()) { throw new EmptyStackException(); } else { return stack[topIndex]; } } @Override public boolean isEmpty() { return topIndex < 0; } @Override public void clear() { for(int i = 0; i <= topIndex; i++) { stack[i] = null; } topIndex = -1; } private void ensureCapacity() { if(topIndex == stack.length - 1) { int newLength = 2 * stack.length; checkCapacity(newLength); stack = Arrays.copyOf(stack, newLength); } } private void checkCapacity(int capacity) { if (capacity > MAX_CAPACITY) { throw new IllegalStateException("Attempt to create a stack whose capacity exceeds allowed maximum"); } } @Override public char setResult(int result) { return 0; } @Override public int getResult() { return 0; } } 

StackInterface

package StackPackage; public interface StackInterface { public void push(T newEntry); public T pop(); public T peek(); public boolean isEmpty(); public void clear(); public char setResult(int result); public int getResult(); }

TreePackage (8Classes)

AVLTree

package TreePackage; public class AVLTree> extends BinarySearchTree implements SearchTreeInterface { public AVLTree() { super(); } public AVLTree(T rootEntry) { super(rootEntry); } // Other methods in SearchTreeInterface are inherited from BinarySearchTree // Corrects an imbalance at the node closest to a structural change in the left subtree of the node's left child // nodeN is a node, closest to the newly added leaf, at which an imbalance occurs and that has a left child private BinaryNode rotateRight(BinaryNode nodeN) { BinaryNode nodeC = nodeN.getLeftChild(); nodeN.setLeftChild(nodeC.getRightChild()); nodeC.setRightChild(nodeN); return nodeC; } private BinaryNode rotateLeft(BinaryNode nodeN) { // TODO  return nodeN; } private BinaryNode rotateRightLeft(BinaryNode nodeN) { BinaryNode nodeC = nodeN.getRightChild(); nodeN.setRightChild(rotateRight(nodeC)); return rotateLeft(nodeN); } private BinaryNode rotateLeftRight(BinaryNode nodeN) { // TODO  return nodeN; } public T add(T newEntry) { T result = null; if(isEmpty()) setRootNode(new BinaryNode<>(newEntry)); else { BinaryNode rootNode = getRootNode(); result = addEntry(rootNode, newEntry); setRootNode(rebalance(rootNode)); } return result; } private T addEntry(BinaryNode rootNode, T newEntry) { T result = null; int comparison = newEntry.compareTo(rootNode.getData()); if (comparison == 0) { result = rootNode.getData(); rootNode.setData(newEntry); } else if (comparison < 0) { if (rootNode.hasLeftChild()) { BinaryNode leftChild = rootNode.getLeftChild(); result = addEntry(leftChild, newEntry); rootNode.setLeftChild(rebalance(leftChild)); } else rootNode.setLeftChild(new BinaryNode<>(newEntry)); } else { if(rootNode.hasRightChild()) { BinaryNode rightChild = rootNode.getRightChild(); result = addEntry(rightChild, newEntry); rootNode.setRightChild(rebalance(rightChild)); } else rootNode.setRightChild(new BinaryNode<>(newEntry)); } return result; } private BinaryNode rebalance(BinaryNode nodeN) { int heightDifference = getHeightDifference(nodeN); if (heightDifference > 1) { // left subtree is taller by more than 1, so addition was in left subtree if (getHeightDifference(nodeN.getLeftChild()) > 0) { // addition was in left subtree of left child nodeN = rotateRight(nodeN); } else { // addition was in right subtree of left child nodeN = rotateLeftRight(nodeN); } } else if (heightDifference < -1) { // right subtree is taller by more than 1, so addition was in right subtree if (getHeightDifference(nodeN.getRightChild()) < 0) { // addition was in right subtree of right child nodeN = rotateLeft(nodeN); } else { // addition was in left subtree of right child nodeN = rotateRightLeft(nodeN); } } return nodeN; } private int getHeightDifference(BinaryNode nodeN) { // TODO  return 1; } }

BinaryNode

package TreePackage; class BinaryNode { private T data; private BinaryNode leftChild; private BinaryNode rightChild; public BinaryNode() { this(null); } public BinaryNode(T dataPortion) { this(dataPortion, null, null); } public BinaryNode(T dataPortion, BinaryNode newLeftChild, BinaryNode newRightChild) { data = dataPortion; leftChild = newLeftChild; rightChild = newRightChild; } public T getData() { return data; } public void setData(T newData) { data = newData; } public BinaryNode getLeftChild() { return leftChild; } public void setLeftChild(BinaryNode newLeftChild) { leftChild = newLeftChild; } public boolean hasLeftChild() { return leftChild != null; } public BinaryNode getRightChild() { return rightChild; } public void setRightChild(BinaryNode newRightChild) { rightChild = newRightChild; } public boolean hasRightChild() { return rightChild != null; } public boolean isLeaf() { return (leftChild == null) && (rightChild == null); } /** counts the nodes in the subtree rooted at this node  * @return The number of nodes in the subtree rooted at this node  */  public int getNumberOfNodes() { int leftNumber = 0; int rightNumber = 0; if (leftChild != null) { leftNumber = leftChild.getNumberOfNodes(); } if (rightChild != null) { rightNumber = rightChild.getNumberOfNodes(); } return 1 + leftNumber + rightNumber; } /** Computes the height of the subtree rooted at this node  * @return The height of the subtree rooted at this node  */  public int getHeight() { return getHeight(this); } private int getHeight(BinaryNode node) { int height = 0; if(node != null) { height = 1 + Math.max(getHeight(node.getLeftChild()), getHeight(node.getRightChild())); } return height; } /** Copies the subtree rooted at this node  * @return The root of a copy of the subtree rooted at this node.  */  public BinaryNode copy() { BinaryNode newRoot = new BinaryNode<>(data); if(leftChild != null) { newRoot.setLeftChild(leftChild.copy()); } if(rightChild != null) { newRoot.setRightChild(rightChild.copy()); } return newRoot; } }

BinarySearchTree

package TreePackage; public class BinarySearchTree> extends BinaryTree implements SearchTreeInterface { public BinarySearchTree() { super(); } public BinarySearchTree(T rootEntry) { super(); setRootNode(new BinaryNode<>(rootEntry)); } @Override public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree) { throw new UnsupportedOperationException(); } @Override public T getEntry(T anEntry) { return findEntry(getRootNode(), anEntry); } private T findEntry(BinaryNode rootNode, T anEntry) { T result = null; if(rootNode != null) { T rootEntry = rootNode.getData(); if(anEntry.equals(rootEntry)) { result = rootEntry; } else if(anEntry.compareTo(rootEntry) < 0) { result = findEntry(rootNode.getLeftChild(), anEntry); } else { result = findEntry(rootNode.getRightChild(), anEntry); } } return result; } @Override public T add(T anEntry) { T result = null; if(isEmpty()) setRootNode(new BinaryNode<>(anEntry)); else result = addIterative(getRootNode(), anEntry); return result; } private T addIterative(BinaryNode rootNode, T anEntry) { // TODO  return null; } @Override public T remove(T anEntry) { ReturnObject oldEntry = new ReturnObject(null); BinaryNode newRoot = removeEntry(getRootNode(), anEntry, oldEntry); setRootNode(newRoot); return oldEntry.getData(); } private BinaryNode removeEntry(BinaryNode rootNode, T anEntry, ReturnObject oldEntry) { if (rootNode != null) { T rootData = rootNode.getData(); int comparison = anEntry.compareTo(rootData); if (comparison == 0) // anEntry is in the root entry of this subtree { oldEntry.setData(rootData); rootNode = removeFromRoot(rootNode); } else if (comparison < 0) // anEntry < root entry { BinaryNode leftChild = rootNode.getLeftChild(); BinaryNode subTreeRoot = removeEntry(leftChild, anEntry, oldEntry); rootNode.setLeftChild(subTreeRoot); } else { BinaryNode rightChild = rootNode.getRightChild(); BinaryNode subTreeRoot = removeEntry(rightChild, anEntry, oldEntry); rootNode.setRightChild(subTreeRoot); } } return rootNode; } private BinaryNode removeFromRoot(BinaryNode rootNode) { // Case 1: rootNode has two children if (rootNode.hasLeftChild() && rootNode.hasRightChild()) { // find node with largest entry in left subtree BinaryNode leftSubtreeRoot = rootNode.getLeftChild(); BinaryNode largestNode = findLargest(leftSubtreeRoot); // replace entry in root with largest from left subtree rootNode.setData(largestNode.getData()); // remove node with largest entry in left subtree rootNode.setLeftChild(removeLargest(leftSubtreeRoot)); } // Case 2: rootNode has at most one child else if (rootNode.hasRightChild()) rootNode = rootNode.getRightChild(); else rootNode = rootNode.getLeftChild(); return rootNode; } // Finds the node containing the largest entry in a given tree // rootNode is the root node of the tree // Returns the node containing the largest entry in the tree. private BinaryNode findLargest(BinaryNode rootNode) { if (rootNode.hasRightChild()) rootNode = findLargest(rootNode.getRightChild()); return rootNode; } // Removes the node containing the largest entry in a given tree // rootNode is the root node of the tree // Returns the root node of the revised tree. private BinaryNode removeLargest(BinaryNode rootNode) { if (rootNode.hasRightChild()) { BinaryNode rightChild = rootNode.getRightChild(); rightChild = removeLargest(rightChild); rootNode.setRightChild(rightChild); } else rootNode = rootNode.getLeftChild(); return rootNode; } public T getMax() { return null; } public T getMin() { return null; } private class ReturnObject { private T data; public ReturnObject(T newData) { data = newData; } public void setData(T newData) { data = newData; } public T getData() { return data; } } private T addEntry(BinaryNode rootNode, T anEntry) { T result = null; int comparison = anEntry.compareTo(rootNode.getData()); if(comparison == 0) { result = rootNode.getData(); rootNode.setData(anEntry); } else if(comparison < 0) { if(rootNode.hasLeftChild()) result = addEntry(rootNode.getLeftChild(), anEntry); else rootNode.setLeftChild(new BinaryNode<>(anEntry)); } else { if(rootNode.hasRightChild()) result = addEntry(rootNode.getRightChild(), anEntry); else rootNode.setRightChild(new BinaryNode<>(anEntry)); } return result; } @Override public boolean contains(T anEntry) { return getEntry(anEntry) != null; } }

BinaryTree

import java.util.Collection; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Queue; import java.util.function.Predicate; import QueuePackage.LinkedQueue; import QueuePackage.QueueInterface; import StackPackage.*; public class BinaryTree implements BinaryTreeInterface { protected BinaryNode root; public BinaryTree() { root = null; } public BinaryTree(T rootData) { root = new BinaryNode<>(rootData); } public BinaryTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { initializeTree(rootData, leftTree, rightTree); } protected void setRootNode(BinaryNode rootNode) { root = rootNode; } @Override public T getRootData() { if(!isEmpty()) { return root.getData(); } return null; } @Override public int getHeight() { return root.getHeight(); } @Override public int getNumberOfNodes() { return root.getNumberOfNodes(); } @Override public Iterator getPostorderIterator() { return null; } @Override public void clear() { root = null; } @Override public Iterator getInorderIterator() { return new InOrderIterator(); } @Override public Iterator getLevelOrderIterator() { return new LevelOrderIterator(); } @Override public Iterator getPreorderIterator() { return null; } @Override public void setTree(T rootData) { setTree(rootData, null, null); } @Override public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree) { initializeTree(rootData, (BinaryTree) leftTree, (BinaryTree) rightTree); } private void initializeTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { root = new BinaryNode<>(rootData); if((leftTree != null) && !leftTree.isEmpty()) root.setLeftChild(leftTree.root); if((rightTree != null) && !rightTree.isEmpty()) { if (rightTree != leftTree) { root.setRightChild(rightTree.root); } else root.setRightChild(rightTree.root.copy()); } if((leftTree != null) && (leftTree != this)) { leftTree.clear(); } if((rightTree != null) && (rightTree != this)) { rightTree.clear(); } } @Override public boolean isEmpty() { return root == null; } // traversal that doesn't use an iterator (for demonstration purposes only) public void iterativeInorderTraverse() { StackInterface> nodeStack = new ArrayStack<>(); BinaryNode currentNode = root; while (!nodeStack.isEmpty() || (currentNode != null)) { while (currentNode != null) { nodeStack.push(currentNode); currentNode = currentNode.getLeftChild(); } if (!nodeStack.isEmpty()) { BinaryNode nextNode = nodeStack.pop(); System.out.println(nextNode.getData()); currentNode = nextNode.getRightChild(); } } } BinaryNode getRootNode() { return root; } private class LevelOrderIterator implements Iterator { private Queue> queue; private QueueInterface> nodeQueue; public LevelOrderIterator() { nodeQueue = new LinkedQueue<>(); if(root != null) { nodeQueue.enqueue(root); } } @Override public boolean hasNext() { return !nodeQueue.isEmpty(); } @Override public T next() { BinaryNode nextNode; if(hasNext()) { nextNode = nodeQueue.dequeue(); BinaryNode leftChild = nextNode.getLeftChild(); BinaryNode rightChild = nextNode.getRightChild(); if(leftChild != null) { nodeQueue.enqueue(leftChild); } if(rightChild != null) { nodeQueue.enqueue(rightChild); } } else { throw new NoSuchElementException(); } return nextNode.getData(); } } private class InOrderIterator implements Iterator { private StackInterface> nodeStack; private BinaryNode currentNode; public InOrderIterator() { nodeStack = new ArrayStack<>(); currentNode = root; } @Override public boolean hasNext() { return !nodeStack.isEmpty() || (currentNode != null); } @Override public T next() { BinaryNode nextNode = null; // find leftmost node with no left child while(currentNode != null) { nodeStack.push(currentNode); currentNode = currentNode.getLeftChild(); } if(!nodeStack.isEmpty()) { nextNode = nodeStack.pop(); currentNode = nextNode.getRightChild(); } else throw new NoSuchElementException(); return nextNode.getData(); } } } 

BinaryTreeInterface

package TreePackage; public interface BinaryTreeInterface extends TreeInterface, TreeIteratorInterface { /** Sets this binary tree to a new one-node binary tree  * @param rootData The object that is the data for the new tree's root*/  void setTree(T rootData); /** Sets this binary tree to a new binary tree  * @param rootData The object that is the data for the new tree's root  * @param leftTree The left subtree of the new tree.  * @param rightTree The right subtree of the new tree. */  void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree); } 

SearchTreeInterface

package TreePackage; import java.util.Iterator; public interface SearchTreeInterface> extends TreeInterface { /** Searches for a specific entry in this tree.  * @param anEntry An object to be found  * @return True if the object was found in the tree */  boolean contains(T anEntry); /** Retrieves a specific entry in this tree  * @param anEntry an object to be found  * @return Either that object that was found in the tree or null if no such object exists */  T getEntry(T anEntry); /** Adds a new entry to this tree, if it does not match an existing object in the tree.  * Otherwise, replaces the existing object with the new entry  * @param anEntry An object to be added to the tree  * @return Either null if anyEntry was not in the tree but has been added, or the existing  * entry that matched the parameter anEntry and has been replaced in the tree */  T add(T anEntry); /** Removes a specific entry from this tree  * @param anEntry An object to be removed  * @return Either the object that was removed from the tree or null if no such object exists  */  T remove(T anEntry); /** Creates an iterator that traverses all entries in this tree.  * @return An iterator that provides sequential and ordered access to the entries in this tree  */  public Iterator getInorderIterator(); public T getMin(); public T getMax(); } 

TreeInterface

package TreePackage; public interface TreeInterface { T getRootData(); int getHeight(); int getNumberOfNodes(); boolean isEmpty(); void clear(); } 

TreeIteratorInterface

package TreePackage; import java.util.Iterator; public interface TreeIteratorInterface { Iterator getPreorderIterator(); Iterator getPostorderIterator(); Iterator getInorderIterator(); Iterator getLevelOrderIterator(); } 

And A driver program

import java.util.Iterator; public class Driver { public static void main(String[] args) { AVLTree tree = new AVLTree<>(); tree.add(60); tree.add(50); tree.add(20); tree.add(80); tree.add(90); tree.add(70); tree.add(55); tree.add(10); tree.add(40); tree.add(35); Iterator iterator = tree.getLevelOrderIterator(); while(iterator.hasNext()) { System.out.print(iterator.next()); if(iterator.hasNext()) { System.out.print(", "); } } } }

PLEASE HELP!!!!

THANK YOU!!!