Need Help With Client Please !!!

(Stack&Queue Package)

LinkedQueue.java

package stackAndQueuePackage; public class LinkedQueue implements QueueInterface { private Node firstNode; // references node at front of queue private Node lastNode; // references node at back of queue public LinkedQueue() { firstNode = null; lastNode = null; } // end default constructor public void enqueue(T newEntry) { Node newNode = new Node(newEntry, null); if (isEmpty()) firstNode = newNode; else lastNode.setNextNode(newNode);

lastNode = newNode; } // end enqueue

public T getFront() { T front = null; if (!isEmpty()) front = firstNode.getData(); return front; } // end getFront

public T dequeue() { T front = null; if (!isEmpty()) { front = firstNode.getData(); firstNode = firstNode.getNextNode(); if (firstNode == null) lastNode = null; } // end if return front; } // end dequeue public boolean isEmpty() { return (firstNode == null) && (lastNode == null); } // end isEmpty public void clear() { firstNode = null; lastNode = null; } // end clear

private class Node { private T data; // entry in queue private Node next; // link to next node

private Node(T dataPortion) { data = dataPortion; next = null; } // end constructor private Node(T dataPortion, Node linkPortion) { data = dataPortion; next = linkPortion; } // end constructor

private T getData() { return data; } // end getData

private void setData(T newData) { data = newData; } // end setData

private Node getNextNode() { return next; } // end getNextNode private void setNextNode(Node nextNode) { next = nextNode; } // end setNextNode } // end Node } // end Linkedqueue

LinkedStack.java

package stackAndQueuePackage; public class LinkedStack implements StackInterface { private Node topNode; // references the last node in the chain public LinkedStack() { topNode = null; } // end default constructor public void push(T newEntry) { Node newNode = new Node(newEntry, topNode); topNode = newNode; } // end push

public T peek() { T top = null; if (topNode != null) top = topNode.getData(); return top; } // end peek

public T pop() { T top = null; if (topNode != null) { top = topNode.getData(); topNode = topNode.getPreviousNode(); } // end if return top; } // end pop

public boolean isEmpty() { return topNode == null; } // end isEmpty public void clear() { topNode = null; } // end clear

private class Node { private T data; // entry in stack private Node previous; // link to previous node

private Node(T dataPortion) { data = dataPortion; previous = null; } // end constructor

private Node(T dataPortion, Node linkPortion) { data = dataPortion; previous = linkPortion; } // end constructor

private T getData() { return data; } // end getData

private void setData(T newData) { data = newData; } // end setData

private Node getPreviousNode() { return previous; } // end getPreviousNode

private void setPreviousNode(Node previousNode) { previous = previousNode; } // end setPreviousNode } // end Node } // end LinkedStack

QueueInterface.java

package stackAndQueuePackage; /** An interface for the ADT queue. @author Frank M. Carrano @version 3.0 */ public interface QueueInterface { /** Adds a new entry to the back of this queue. @param newEntry an object to be added */ public void enqueue(T newEntry);

/** Removes and returns the entry at the front of this queue. @return either the object at the front of the queue or, if the queue is empty before the operation, null */ public T dequeue();

/** Retrieves the entry at the front of this queue. @return either the object at the front of the queue or, if the queue is empty, null */ public T getFront();

/** Detects whether this queue is empty. @return true if the queue is empty, or false otherwise */ public boolean isEmpty();

/** Removes all entries from this queue. */ public void clear(); } // end QueueInterface

StackInterface.java

package stackAndQueuePackage; /** An interface for the ADT stack. @author Frank M. Carrano @version 3.0 */ public interface StackInterface { /** Adds a new entry to the top of this stack. @param newEntry an object to be added to the stack */ public void push(T newEntry); /** Removes and returns this stacks top entry. @return either the object at the top of the stack or, if the stack is empty before the operation, null */ public T pop(); /** Retrieves this stacks top entry. @return either the object at the top of the stack or null if the stack is empty */ public T peek(); /** Detects whether this stack is empty. @return true if the stack is empty */ public boolean isEmpty(); /** Removes all entries from this stack */ public void clear(); } // end StackInterface

Tree Package

BinaryNode.java

package treePackage; /** A class that represents nodes in a binary tree. @author Frank M. Carrano @version 3.0 */ class BinaryNode implements BinaryNodeInterface { private T data; private BinaryNode left; private BinaryNode right;

public BinaryNode() { this(null); // call next constructor } // end default constructor

public BinaryNode(T dataPortion) { this(dataPortion, null, null); // call next constructor } // end constructor

public BinaryNode(T dataPortion, BinaryNode leftChild, BinaryNode rightChild) { data = dataPortion; left = leftChild; right = rightChild; } // end constructor

public T getData() { return data; } // end getData

public void setData(T newData) { data = newData; } // end setData

public BinaryNodeInterface getLeftChild() { return left; } // end getLeftChild

public BinaryNodeInterface getRightChild() { return right; } // end getRightChild

public void setLeftChild(BinaryNodeInterface leftChild) { left = (BinaryNode)leftChild; } // end setLeftChild

public void setRightChild(BinaryNodeInterface rightChild) { right = (BinaryNode)rightChild; } // end setRightChild

public boolean hasLeftChild() { return left != null; } // end hasLeftChild

public boolean hasRightChild() { return right != null; } // end hasRightChild

public boolean isLeaf() { return (left == null) && (right == null); } // end isLeaf

public BinaryNodeInterface copy() { BinaryNode newRoot = new BinaryNode(data);

if (left != null) newRoot.left = (BinaryNode)left.copy(); if (right != null) newRoot.right = (BinaryNode)right.copy(); return newRoot; } // end copy

public int getHeight() { return getHeight(this); // call private getHeight } // end getHeight

private int getHeight(BinaryNode node) { int height = 0;

if (node != null) height = 1 + Math.max(getHeight(node.left), getHeight(node.right)); return height; } // end getHeight

public int getNumberOfNodes() { int leftNumber = 0; int rightNumber = 0;

if (left != null) leftNumber = left.getNumberOfNodes(); if (right != null) rightNumber = right.getNumberOfNodes(); return 1 + leftNumber + rightNumber; } // end getNumberOfNodes } // end BinaryNode

BinaryNodeInterface.java

package treePackage; /** An interface for a node in a binary tree. @author Frank M. Carrano @version 3.0 */ interface BinaryNodeInterface { /** Retrieves the data portion of this node. @return the object in the data portion of the node */ public T getData();

/** Sets the data portion of this node. @param newData the data object */ public void setData(T newData);

/** Retrieves the left child of this node. @return the node that is this nodes left child */ public BinaryNodeInterface getLeftChild();

/** Retrieves the right child of this node. @return the node that is this nodes right child */ public BinaryNodeInterface getRightChild();

/** Sets this nodes left child to a given node. @param leftChild a node that will be the left child */ public void setLeftChild(BinaryNodeInterface leftChild);

/** Sets this nodes right child to a given node. @param rightChild a node that will be the right child */ public void setRightChild(BinaryNodeInterface rightChild);

/** Detects whether this node has a left child. @return true if the node has a left child */ public boolean hasLeftChild();

/** Detects whether this node has a right child. @return true if the node has a right child */ public boolean hasRightChild();

/** Detects whether this node is a leaf. @return true if the node is a leaf */ public boolean isLeaf();

/** 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();

/** Computes the height of the subtree rooted at this node. @return the height of the subtree rooted at this node */ public int getHeight();

/** Copies the subtree rooted at this node. @return the root of a copy of the subtree rooted at this node */ public BinaryNodeInterface copy(); } // end BinaryNodeInterface

BinaryTree.java

package treePackage; import java.util.Iterator; import java.util.NoSuchElementException; import stackAndQueuePackage.*;

/** A class that implements the ADT binary tree. @author Frank M. Carrano @version 3.0 */ public class BinaryTree implements BinaryTreeInterface { private BinaryNodeInterface 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 BinaryNode copyNodes() // not essential { return (BinaryNode)root.copy(); } // end copyNodes

public T getRootData() { T rootData = null;

if (root != null) rootData = root.getData(); return rootData; } // end getRootData

public boolean isEmpty() { return root == null; } // end isEmpty

public void clear() { root = null; } // end clear

protected void setRootData(T rootData) { root.setData(rootData); } // end setRootData

protected void setRootNode(BinaryNodeInterface rootNode) { root = rootNode; } // end setRootNode

protected BinaryNodeInterface getRootNode() { return root; } // end getRootNode

public int getHeight() { return root.getHeight(); } // end getHeight

public int getNumberOfNodes() { return root.getNumberOfNodes(); } // end getNumberOfNodes

public Iterator getPreorderIterator() { return new PreorderIterator(); } // end getPreorderIterator

public Iterator getInorderIterator() { return new InorderIterator(); } // end getInorderIterator public Iterator getPostorderIterator() { return new PostorderIterator(); } // end getPostorderIterator

public Iterator getLevelOrderIterator() { return new LevelOrderIterator(); } // end getLevelOrderIterator

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() { BinaryNodeInterface nextNode; if (hasNext()) { nextNode = nodeStack.pop(); BinaryNodeInterface leftChild = nextNode.getLeftChild(); BinaryNodeInterface 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

private class InorderIterator implements Iterator { private StackInterface> nodeStack; private BinaryNodeInterface currentNode;

public InorderIterator() { nodeStack = new LinkedStack>(); currentNode = root; } // end default constructor

public boolean hasNext() { return !nodeStack.isEmpty() || (currentNode != null); } // end hasNext

public T next() { BinaryNodeInterface 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

private class PostorderIterator implements Iterator { private StackInterface> nodeStack; private BinaryNodeInterface currentNode; public PostorderIterator() { nodeStack = new LinkedStack>(); currentNode = root; } // end default constructor public boolean hasNext() { return !nodeStack.isEmpty() || (currentNode != null); } // end hasNext public T next() { boolean foundNext = false; BinaryNodeInterface 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

BinaryNodeInterface parent = nodeStack.peek(); if (parent != null && nextNode == parent.getLeftChild()) currentNode = parent.getRightChild(); 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() { BinaryNodeInterface nextNode; if (hasNext()) { nextNode = nodeQueue.dequeue(); BinaryNodeInterface leftChild = nextNode.getLeftChild(); BinaryNodeInterface 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

BinaryTreeInterface.java

package treePackage; /** An interface for the ADT binary tree. @author Frank M. Carrano @version 3.0 */ public interface BinaryTreeInterface extends TreeInterface, TreeIteratorInterface { /** Sets an existing binary tree to a new one-node binary tree. @param rootData an object that is the data in the new trees root */ public void setTree(T rootData);

/** Sets an existing binary tree to a new binary tree. @param rootData an object that is the data in the new trees root @param leftTree the left subtree of the new tree @param rightTree the right subtree of the new tree */ public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree); } // end BinaryTreeInterface

TreeInterface.java

package treePackage; /** An interface for the ADT tree. @author Frank M. Carrano @version 3.0 */ public interface TreeInterface { public T getRootData(); public int getHeight(); public int getNumberOfNodes(); public boolean isEmpty(); public void clear(); } // end TreeInterface

TreeIteratorInterface.java

package treePackage; import java.util.Iterator; /** An interface of iterators for the ADT tree. @author Frank M. Carrano @version 3.0 */ public interface TreeIteratorInterface { public Iterator getPreorderIterator(); public Iterator getPostorderIterator(); public Iterator getInorderIterator(); public Iterator getLevelOrderIterator(); } // end TreeIteratorInterface

ClientBinaryTree.java

import java.util.Iterator;

import treePackage.*;

public class ClientBinaryTree {

public static void createTree(BinaryTree rootNode) { // Create the nodes at level 2

// Create the nodes at level 3

// Create the nodes at level 4

// Set values to the leaves at level 4 level4Node1.setTree("F", null, null); // no children // Set values to the nodes at level 3

// Set values to the nodes at level 2 level2Node1.setTree("B", level3Node1, level3Node2);

// Set values to the root at level 1

} public static void traverseTree(BinaryTree rootNode) { System.out.println(" Inorder traversal:"); System.out.println("Expected: D B F E G A C H "); System.out.print("Actual: "); Iterator iter = rootNode.getInorderIterator(); while (iter.hasNext()) { System.out.print(iter.next() + " "); } System.out.println();

System.out.println(" Preorder traversal:"); System.out.println("Expected: A B D E F G C H"); System.out.print("Actual: "); iter = rootNode.getPreorderIterator(); while (iter.hasNext()) { System.out.print(iter.next() + " "); } System.out.println();

System.out.println(" Postorder traversal:"); System.out.println("Expected: D F G E B H C A "); System.out.print("Actual: "); iter = rootNode.getPostorderIterator(); while (iter.hasNext()) { System.out.print(iter.next() + " "); } System.out.println();

System.out.println(" Level order traversal:"); System.out.println("Expected: A B C D E H F G "); System.out.print("Actual: "); iter = rootNode.getLevelOrderIterator(); while (iter.hasNext()) { System.out.print(iter.next() + " "); } System.out.println(); }

public static void main(String[] args) {

BinaryTree rootNode = new BinaryTree(); createTree(rootNode); traverseTree(rootNode); }

}