Please help write BinaryTree.java Thank you!
Create a class BinaryTree. A class that implements the ADT binary tree.
import java.util.Iterator; import java.util.NoSuchElementException;
import StackAndQueuePackage.*; public class BinaryTree implements BinaryTreeInterface { private BinaryNode root;
public BinaryTree() { root = null; } // end default constructor
public BinaryTree(T rootData) { root = new BinaryNode<>(rootData); } // end constructor
public BinaryTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { privateSetTree(rootData, leftTree, rightTree); } // end constructor
public void setTree(T rootData) { root = new BinaryNode<>(rootData); } // end setTree
public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree) { privateSetTree(rootData, (BinaryTree)leftTree, (BinaryTree)rightTree); } // end setTree
private void privateSetTree(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()); } // end if
if ((leftTree != null) && (leftTree != this)) leftTree.clear(); if ((rightTree != null) && (rightTree != this)) rightTree.clear(); } // end privateSetTree
//...
private class PreorderIterator implements Iterator { private StackInterface> nodeStack; public PreorderIterator() { nodeStack = new LinkedStack<>(); if (root != null) nodeStack.push(root); } // end default constructor public boolean hasNext() { return !nodeStack.isEmpty(); } // end hasNext public T next() { BinaryNode nextNode; if (hasNext()) { nextNode = nodeStack.pop(); BinaryNode leftChild = nextNode.getLeftChild(); BinaryNode rightChild = nextNode.getRightChild(); // Push into stack in reverse order of recursive calls if (rightChild != null) nodeStack.push(rightChild); if (leftChild != null) nodeStack.push(leftChild); } else { throw new NoSuchElementException(); } return nextNode.getData(); } // end next public void remove() { throw new UnsupportedOperationException(); } // end remove } // end PreorderIterator
public void iterativePreorderTraverse() { StackInterface> nodeStack = new LinkedStack<>(); if (root != null) nodeStack.push(root); BinaryNode nextNode; while (!nodeStack.isEmpty()) { nextNode = nodeStack.pop(); BinaryNode leftChild = nextNode.getLeftChild(); BinaryNode rightChild = nextNode.getRightChild(); // Push into stack in reverse order of recursive calls if (rightChild != null) nodeStack.push(rightChild); if (leftChild != null) nodeStack.push(leftChild); System.out.print(nextNode.getData() + " "); } // end while } // end iterativePreorderTraverse private class InorderIterator implements Iterator { private StackInterface> nodeStack; private BinaryNode currentNode;
public InorderIterator() { nodeStack = new LinkedStack<>(); currentNode = root; } // end default constructor
public boolean hasNext() { return !nodeStack.isEmpty() || (currentNode != null); } // end hasNext
public T next() { BinaryNode nextNode = null;
// Find leftmost node with no left child while (currentNode != null) { nodeStack.push(currentNode); currentNode = currentNode.getLeftChild(); } // end while
// Get leftmost node, then move to its right subtree if (!nodeStack.isEmpty()) { nextNode = nodeStack.pop(); assert nextNode != null; // Since nodeStack was not empty // before the pop currentNode = nextNode.getRightChild(); } else throw new NoSuchElementException();
return nextNode.getData(); } // end next
public void remove() { throw new UnsupportedOperationException(); } // end remove } // end InorderIterator
public void iterativeInorderTraverse() { StackInterface> nodeStack = new LinkedStack<>(); BinaryNode currentNode = root; while (!nodeStack.isEmpty() || (currentNode != null)) { // Find leftmost node with no left child while (currentNode != null) { nodeStack.push(currentNode); currentNode = currentNode.getLeftChild(); } // end while // Visit leftmost node, then traverse its right subtree if (!nodeStack.isEmpty()) { BinaryNode nextNode = nodeStack.pop(); assert nextNode != null; // Since nodeStack was not empty // before the pop System.out.print(nextNode.getData() + " "); currentNode = nextNode.getRightChild(); } // end if } // end while } // end iterativeInorderTraverse private class PostorderIterator implements Iterator { private StackInterface> nodeStack; private BinaryNode currentNode; public PostorderIterator() { nodeStack = new LinkedStack<>(); currentNode = root; } // end default constructor public boolean hasNext() { return !nodeStack.isEmpty() || (currentNode != null); } // end hasNext public T next() { BinaryNode leftChild, rightChild, nextNode = null; // Find leftmost leaf while (currentNode != null) { nodeStack.push(currentNode); leftChild = currentNode.getLeftChild(); if (leftChild == null) currentNode = currentNode.getRightChild(); else currentNode = leftChild; } // end while // Stack is not empty either because we just pushed a node, or // it wasn't empty to begin with since hasNext() is true. // But Iterator specifies an exception for next() in case // hasNext() is false. if (!nodeStack.isEmpty()) { nextNode = nodeStack.pop(); // nextNode != null since stack was not empty before pop BinaryNode parent = null; if (!nodeStack.isEmpty()) { parent = nodeStack.peek(); if (nextNode == parent.getLeftChild()) currentNode = parent.getRightChild(); else currentNode = null; } else currentNode = null; } else { throw new NoSuchElementException(); } // end if return nextNode.getData(); } // end next public void remove() { throw new UnsupportedOperationException(); } // end remove } // end PostorderIterator private class LevelOrderIterator implements Iterator { private QueueInterface> nodeQueue; public LevelOrderIterator() { nodeQueue = new LinkedQueue<>(); if (root != null) nodeQueue.enqueue(root); } // end default constructor public boolean hasNext() { return !nodeQueue.isEmpty(); } // end hasNext public T next() { BinaryNode nextNode; if (hasNext()) { nextNode = nodeQueue.dequeue(); BinaryNode leftChild = nextNode.getLeftChild(); BinaryNode rightChild = nextNode.getRightChild(); // Add to queue in order of recursive calls if (leftChild != null) nodeQueue.enqueue(leftChild);
if (rightChild != null) nodeQueue.enqueue(rightChild); } else { throw new NoSuchElementException(); } return nextNode.getData(); } // end next public void remove() { throw new UnsupportedOperationException(); } // end remove } // end LevelOrderIterator } // end BinaryTree
