Java

- Write a getAllEntriesLessThanIterative method for the BinarySEarchTreewithDublicates Class.

This method returns an ArrayList of all entries in the tree less than a target.

Use iteration.

- Write a getAllEntriesIterative method.

Use iteration.

This method returns an ArrayList of all the entries in a tree that match a target.

import java.util.ArrayList;

import java.util.Collections;

import java.util.Iterator;

import java.util.Stack;

public class BinarySearchTreeWithDups> extends BinarySearchTree

implements SearchTreeInterface, java.io.Serializable {

public BinarySearchTreeWithDups() {

super();

}

public BinarySearchTreeWithDups(T rootEntry) {

super(rootEntry);

setRootNode(new BinaryNode(rootEntry));

}

@Override

public T add(T newEntry) {

T result = null;

if (isEmpty())

setRootNode(new BinaryNode(newEntry));

else

result = addEntryHelperIterative(newEntry);

return result;

}

// ??? IMPLEMENT THIS METHOD

private T addEntryHelperIterative(T newEntry)

{

BinaryNodeInterface currentNode = getRootNode();

assert currentNode != null;

T result = null;

boolean found = false;

while (!found)

{

T currentEntry = currentNode.getData();

int comparison = newEntry.compareTo(currentEntry);

if (comparison == 0)

{

// result = currentEntry;

result = newEntry;

if (currentNode.hasRightChild())

currentNode = currentNode.getRightChild();

else

{

found = true;

currentNode.setRightChild(new BinaryNode(newEntry));

}

}

else if (comparison < 0)

{

if (currentNode.hasLeftChild())

currentNode = currentNode.getLeftChild();

else

{

found = true;

currentNode.setLeftChild(new BinaryNode(newEntry));

}

}

else

{

assert comparison > 0;

if (currentNode.hasRightChild())

currentNode = currentNode.getRightChild();

else

{

found = true;

currentNode.setRightChild(new BinaryNode(newEntry));

}

}

}

return result;

}

// ??? IMPLEMENT THIS METHOD

public ArrayList getAllEntriesIterative(T searchVal) {

// this initial code is meant as a suggestion to get your started- feel

// free to use it or delete it!

BinaryNodeInterface currentNode = getRootNode();

ArrayList entryList = new ArrayList();

// while(currentNode!=null) {

// }

return entryList;

}

public ArrayList getAllEntriesRecursive(T searchVal)

{

BinaryNodeInterface rootNode = getRootNode();

ArrayList entryList = new ArrayList();

getAllEntriesHelper(searchVal, rootNode, entryList);

return entryList;

}

private void getAllEntriesHelper(T searchVal, BinaryNodeInterface node,

ArrayList entryList)

{

if(node != null)

{

int compare = node.getData().compareTo(searchVal);

if(compare == 0)

{

getAllEntriesHelper(searchVal, node.getRightChild(), entryList);

entryList.add(node.getData());

}

else

{

getAllEntriesHelper(searchVal, node.getRightChild(), entryList);

getAllEntriesHelper(searchVal, node.getLeftChild(), entryList);

}

}

}

// ??? IMPLEMENT THIS METHOD

public ArrayList getAllEntriesLessThanIterative(T searchVal) {

// this initial code is meant as a suggestion to get your started- feel

// free to use it or delete it!

ArrayList entryList = new ArrayList();

// Hint: consider using a stack to mimic recursion!

// Stack> nodeStack = new

// Stack>();

// nodeStack.push(getRootNode());

// while(!nodeStack.isEmpty()) {

// }

return entryList;

}

public ArrayList getAllEntriesLessThanRecursive(T searchVal)

{

BinaryNodeInterface rootNode = getRootNode();

ArrayList entryList = new ArrayList();

getAllEntriesLessThanHelper(searchVal, rootNode, entryList);

return entryList;

}

public void getAllEntriesLessThanHelper(T searchVal, BinaryNodeInterface node,

ArrayList entryList)

{

if(node != null)

{

if(node.getData().compareTo(searchVal) < 0)

{

entryList.add(node.getData());

}

if(node.getLeftChild() != null)

{

getAllEntriesLessThanHelper(searchVal, node.getLeftChild(), entryList);

}

if(node.getRightChild() != null)

{

getAllEntriesLessThanHelper(searchVal, node.getRightChild(), entryList);

}

}

}

}

public class LabFPartADriver {

public static void main(String[] args) {

System.out.println("Traditional Binary Search Tree- No Dups");

BinarySearchTree nonDupTree = new BinarySearchTree();

nonDupTree.add("E");

nonDupTree.add("B");

nonDupTree.add("C");

nonDupTree.add("A");

nonDupTree.add("H");

nonDupTree.add("D");

nonDupTree.add("F");

nonDupTree.add("G");

System.out.println("Inorder should print ABCDEFGH");

nonDupTree.inorderTraverse();

System.out.println(" Preorder should print EBACDHFG");

nonDupTree.preorderTraverse();

nonDupTree.add("B");

nonDupTree.add("F");

nonDupTree.add("E");

System.out.println(" Inorder should print ABCDEFGH");

nonDupTree.inorderTraverse();

System.out.println(" Binary Search Tree With Dups");

BinarySearchTreeWithDups dupTree = new BinarySearchTreeWithDups();

dupTree.add("E");

dupTree.add("B");

dupTree.add("C");

dupTree.add("A");

dupTree.add("H");

dupTree.add("D");

dupTree.add("F");

dupTree.add("G");

System.out.println("Inorder should print ABCDEFGH");

dupTree.inorderTraverse();

System.out.println(" Preorder should print EBACDHFG");

dupTree.preorderTraverse();

dupTree.add("G");

dupTree.add("B");

dupTree.add("B");

dupTree.add("D");

dupTree.add("E");

dupTree.add("F");

System.out.println(" Inorder should print ABBBCDDEEFFGGH");

dupTree.inorderTraverse();

System.out.println(" Preorder should print EBACBBDDHFEGFG");

dupTree.preorderTraverse();

System.out.println();

System.out.println("getAllIterative should print [B, B, B] " + dupTree.getAllEntriesIterative("B"));

System.out.println("getAllRecursive should print [B, B, B] " + dupTree.getAllEntriesRecursive("B"));

System.out.println("getAllIterative should print [C] " + dupTree.getAllEntriesIterative("C"));

System.out.println("getAllRecursive should print [C] " + dupTree.getAllEntriesRecursive("C"));

System.out.println("getAllIterative should print [] " + dupTree.getAllEntriesIterative("I"));

System.out.println("getAllRecursive should print [] " + dupTree.getAllEntriesRecursive("I"));

// note that print order does not matter, as long as the contents match

// to make testing easier, you might consider invoking Collections.sort on your ArrayList before you return it

System.out.println("getLessThanIterative should print [A, B, B, B, C, D, D] " + dupTree.getAllEntriesLessThanIterative("E"));

System.out.println("getLessThanRecursive should print [A, B, B, B, C, D, D] " + dupTree.getAllEntriesLessThanRecursive("E"));

System.out.println("getLessThanIterative should print [A, B, B, B, C, D, D, E, E, F, F] " + dupTree.getAllEntriesLessThanIterative("G"));

System.out.println("getLessThanRecursive should print [A, B, B, B, C, D, D, E, E, F, F] " + dupTree.getAllEntriesLessThanRecursive("G"));

System.out.println("getLessThanIterative should print [] " + dupTree.getAllEntriesLessThanIterative("A"));

System.out.println("getLessThanRecursive should print [] " + dupTree.getAllEntriesLessThanRecursive("A"));

}

}

import java.util.Iterator;

public interface TreeIteratorInterface {

public Iterator getPreorderIterator();

public Iterator getPostorderIterator();

public Iterator getInorderIterator();

public Iterator getLevelOrderIterator();

}

public interface TreeInterface {

public T getRootData();

public int getHeight();

public int getNumberOfNodes();

public boolean isEmpty();

public void clear();

}

// 26.03

/**

* A class that represents nodes in a binary tree.

*

* @author Frank M. Carrano

* @version 2.0

*/

class BinaryNode implements BinaryNodeInterface,

java.io.Serializable

{

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

// 26.06

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

// 26.11

public int getHeight()

{

return getHeight(this); // call private getHeight

} // end getHeight

// 26.11

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

// 26.11

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

import java.util.Iterator;

/**

* A class that implements the ADT binary search tree by extending BinaryTree.

*

* @author Frank M. Carrano

* @version 2.0

*/

public class BinarySearchTree> extends

BinaryTree implements SearchTreeInterface, java.io.Serializable {

public BinarySearchTree() {

super();

}

public BinarySearchTree(T rootEntry) {

super();

setRootNode(new BinaryNode(rootEntry));

}

public void setTree(T rootData) { // disable setTree (see Segment 27.6)

throw new UnsupportedOperationException();

}

public void setTree(T rootData, BinaryTreeInterface leftTree,

BinaryTreeInterface rightTree) {

throw new UnsupportedOperationException();

}

public T getEntry(T entry) {

T result = null;

boolean found = false;

BinaryNodeInterface currentNode = getRootNode();

while (!found && (currentNode != null)) {

T currentEntry = currentNode.getData();

if (entry.equals(currentEntry)) {

result = currentEntry;

found = true;

} else if (entry.compareTo(currentEntry) < 0)

currentNode = currentNode.getLeftChild();

else

currentNode = currentNode.getRightChild();

}

return result;

}

public boolean contains(T entry) {

return getEntry(entry) != null;

}

public T add(T newEntry) {

T result = null;

if (isEmpty())

setRootNode(new BinaryNode(newEntry));

else

result = addEntry(newEntry);

return result;

}

// 27.18

private T addEntry(T newEntry) {

BinaryNodeInterface currentNode = getRootNode();

assert currentNode != null;

T result = null;

boolean found = false;

while (!found) {

T currentEntry = currentNode.getData();

int comparison = newEntry.compareTo(currentEntry);

if (comparison == 0) { // newEntry matches currentEntry;

// return and replace currentEntry

found = true;

result = currentEntry;

currentNode.setData(newEntry);

} else if (comparison < 0) {

if (currentNode.hasLeftChild())

currentNode = currentNode.getLeftChild();

else {

found = true;

currentNode.setLeftChild(new BinaryNode(newEntry));

} // end if

} else {

assert comparison > 0;

if (currentNode.hasRightChild())

currentNode = currentNode.getRightChild();

else {

found = true;

currentNode.setRightChild(new BinaryNode(newEntry));

}

}

}

return result;

}

public T remove(T entry) {

T result = null;

// locate node (and its parent) that contains a match for entry

NodePair pair = findNode(entry);

BinaryNodeInterface currentNode = pair.getFirst();

BinaryNodeInterface parentNode = pair.getSecond();

if (currentNode != null) { // entry is found

result = currentNode.getData(); // get entry to be removed

// Case 1: currentNode has two children

if (currentNode.hasLeftChild() && currentNode.hasRightChild()) {

// replace entry in currentNode with the entry in another node

// that has at most one child; that node can be deleted

// get node to remove (contains inorder predecessor; has at

// most one child) and its parent

pair = getNodeToRemove(currentNode);

BinaryNodeInterface nodeToRemove = pair.getFirst();

parentNode = pair.getSecond();

// copy entry from nodeToRemove to currentNode

currentNode.setData(nodeToRemove.getData());

currentNode = nodeToRemove;

// Assertion: currentNode is the node to be removed; it has at

// most one child

// Assertion: Case 1 has been transformed to Case 2

} // end if

// Case 2: currentNode has at most one child; delete it

removeNode(currentNode, parentNode);

} // end if

return result;

} // end remove

// Other public methods in SearchTreeInterface are inherited from

// BinaryTree.

// locate node that contains a match for entry

private NodePair findNode(T entry) {

NodePair result = new NodePair();

boolean found = false;

BinaryNodeInterface currentNode = getRootNode();

BinaryNodeInterface parentNode = null;

while (!found && (currentNode != null)) {

T currentEntry = currentNode.getData();

int comparison = entry.compareTo(currentEntry);

if (comparison < 0) {

parentNode = currentNode;

currentNode = currentNode.getLeftChild();

} else if (comparison > 0) {

parentNode = currentNode;

currentNode = currentNode.getRightChild();

} else

found = true;

} // end while

if (found)

result = new NodePair(currentNode, parentNode);

// found entry is currentNode.getData()

return result;

} // end findNode

/**

* Task: Gets the node that contains the inorder predecessor of currentNode.

* Precondition: currentNode has two children

*/

// 27.39

private NodePair getNodeToRemove(BinaryNodeInterface currentNode) {

// find node with largest entry in left subtree by

// moving as far right in the subtree as possible

BinaryNodeInterface leftSubtreeRoot = currentNode.getLeftChild();

BinaryNodeInterface rightChild = leftSubtreeRoot;

BinaryNodeInterface priorNode = currentNode;

while (rightChild.hasRightChild()) {

priorNode = rightChild;

rightChild = rightChild.getRightChild();

} // end while

// rightChild contains the inorder predecessor and is the node to

// remove; priorNode is its parent

return new NodePair(rightChild, priorNode);

} // end getNodeToRemove

/** Task: Removes a node having at most one child. */

// 27.40

private void removeNode(BinaryNodeInterface nodeToRemove,

BinaryNodeInterface parentNode) {

BinaryNodeInterface childNode;

if (nodeToRemove.hasLeftChild())

childNode = nodeToRemove.getLeftChild();

else

childNode = nodeToRemove.getRightChild();

// Assertion: if nodeToRemove is a leaf, childNode is null

assert (nodeToRemove.isLeaf() && childNode == null)

|| !nodeToRemove.isLeaf();

// if nodeToRemove is the root

if (nodeToRemove == getRootNode())

setRootNode(childNode);

// else nodeToRemove is not the root;

// link the parent of nodeToRemove to childNode,

// thereby deleting nodeToRemove

else if (parentNode.getLeftChild() == nodeToRemove)

parentNode.setLeftChild(childNode);

else

parentNode.setRightChild(childNode);

} // end removeNode

private class NodePair {

private BinaryNodeInterface first, second;

public NodePair() {

first = null;

second = null;

} // end default constructor

public NodePair(BinaryNodeInterface firstNode,

BinaryNodeInterface secondNode) {

first = firstNode;

second = secondNode;

} // end constructor

public BinaryNodeInterface getFirst() {

return first;

} // end getFirst

public BinaryNodeInterface getSecond() {

return second;

} // end getSecond

} // end NodePair

} // end BinarySearchTree

import java.util.Iterator;

import java.util.NoSuchElementException;

/**

* A class that implements the ADT binary tree.

*

* @author Frank M. Carrano

* @version 2.0

*/

public class BinaryTree implements BinaryTreeInterface,

java.io.Serializable {

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

// 26.08

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

// 26.09

public T getRootData() {

T rootData = null;

if (root != null)

rootData = root.getData();

return rootData;

} // end getRootData

// 26.09

public boolean isEmpty() {

return root == null;

} // end isEmpty

// 26.09

public void clear() {

root = null;

} // end clear

// 26.09

protected void setRootData(T rootData) {

root.setData(rootData);

} // end setRootData

// 26.09

protected void setRootNode(BinaryNodeInterface rootNode) {

root = rootNode;

} // end setRootNode

// 26.09

protected BinaryNodeInterface getRootNode() {

return root;

} // end getRootNode

// 26.10

public int getHeight() {

return root.getHeight();

} // end getHeight

// 26.10

public int getNumberOfNodes() {

return root.getNumberOfNodes();

} // end getNumberOfNodes

// 26.12

public void inorderTraverse() {

inorderTraverse(root);

} // end inorderTraverse

private void inorderTraverse(BinaryNodeInterface node) {

if (node != null) {

inorderTraverse(node.getLeftChild());

System.out.print(node.getData());

inorderTraverse(node.getRightChild());

} // end if

} // end inorderTraverse

public void preorderTraverse() {

preorderTraverse(root);

}

private void preorderTraverse(BinaryNodeInterface node) {

if(node!=null) {

System.out.print(node.getData());

preorderTraverse(node.getLeftChild());

preorderTraverse(node.getRightChild());

}

}

public Iterator getPreorderIterator() {

return new PreorderIterator();

} // end getPreorderIterator

// 26.13

public Iterator getInorderIterator() {

return new InorderIterator();

} // end getInorderIterator

public Iterator getPostorderIterator() {

return new PostorderIterator();

} // end getPostorderIterator

public Iterator getLevelOrderIterator() {

return new LevelOrderIterator();

} // end getLevelOrderIterator

/*

* // 26.14 ITERATIVE public void inorderTraverse() {

* StackInterface> nodeStack = new

* LinkedStack>(); BinaryNodeInterface 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()) { BinaryNodeInterface nextNode =

* nodeStack.pop(); assert nextNode != null; // since nodeStack was not

* empty // before the pop System.out.println(nextNode.getData());

* currentNode = nextNode.getRightChild(); } // end if } // end while } //

* end inorderTraverse

*

* public void inorderTraverse() // Q5 { StackInterface>

* nodeStack = new LinkedStack>(); BinaryNode currentNode =

* (BinaryNode)root;//(BinaryNode)

*

* while (!nodeStack.isEmpty() || (currentNode != null)) { while

* (currentNode != null) { nodeStack.push(currentNode); currentNode =

* (BinaryNode)currentNode.getLeftChild(); //(BinaryNode) } // end

* while

*

* if (!nodeStack.isEmpty()) { BinaryNode nextNode = nodeStack.pop();

* assert nextNode != null; // since stack was not empty before pop

* System.out.print(nextNode.getData() + " "); currentNode =

* (BinaryNode)nextNode.getRightChild(); //(BinaryNode) } }

* System.out.println(); } // end inorderTraverse

*/

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

// 26.15

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

// 25.18

/** * An interface for the ADT binary tree. * * @author Frank M. Carrano * @version 2.0 */ public interface BinaryTreeInterface extends TreeInterface, TreeIteratorInterface { /** Task: 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); /** Task: 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

/**

* A class that implements the ADT stack by using a chain of nodes.

*

* @author Frank M. Carrano

* @version 2.0

*/

public class LinkedStack implements StackInterface, java.io.Serializable

{

private Node topNode; // references the first node in the chain

public LinkedStack()

{

topNode = null;

} // end default constructor

// 22.03

public void push(T newEntry)

{

Node newNode = new Node(newEntry, topNode);

topNode = newNode;

} // end push

// 22.04

public T peek()

{

T top = null;

if (topNode != null)

top = topNode.getData();

return top;

} // end peek

// 22.05

public T pop()

{

T top = peek();

if (topNode != null)

topNode = topNode.getNextNode();

return top;

} // end pop

/*

// does not call peek (Question 1, Chapter 22)

public T pop()

{

T top = null;

if (topNode != null)

{

top = topNode.getData();

topNode = topNode.getNextNode();

} // end if

return top;

} // end pop

*/

// 22.06

public boolean isEmpty()

{

return topNode == null;

} // end isEmpty

// 22.06

public void clear()

{

topNode = null;

} // end clear

private class Node implements java.io.Serializable

{

private T data; // entry in stack

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 LinkedStack

import java.util.Iterator; /** * An interface for a search tree. * * @author Frank M. Carrano * @version 2.0 */ public interface SearchTreeInterface> extends TreeInterface { /** Task: Searches for a specific entry in the tree. * @param entry an object to be found * @return true if the object was found in the tree */ public boolean contains(T entry); /** Task: Retrieves a specific entry in the tree. * @param entry an object to be found * @return either the object that was found in the tree or * null if no such object exists */ public T getEntry(T entry); /** Task: Adds a new entry to the tree. * If the entry matches an object that exists in the tree * already, replaces the object with the new entry. * @param newEntry an object to be added to the tree * @return either null if newEntry was not in the tree already, or * an existing entry that matched the parameter newEntry * and has been replaced in the tree */ public T add(T newEntry); /** Task: Removes a specific entry from the tree. * @param entry an object to be removed * @return either the object that was removed from the tree or * null if no such object exists */ public T remove(T entry); /** Task: Creates an iterator that traverses all entries in the tree. * @return an iterator that provides sequential and ordered access to * the entries in the tree */ public Iterator getInorderIterator(); } // end SearchTreeInterface

// 21.03 /** * An interface for the ADT stack. * * @author Frank M. Carrano * @version 2.0 */ public interface StackInterface { /** Task: Adds a new entry to the top of the stack. * @param newEntry an object to be added to the stack */ public void push(T newEntry); /** Task: Removes and returns the 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(); /** Task: Retrieves the stacks top entry. * @return either the object at the top of the stack or null if * the stack is empty */ public T peek(); /** Task: Detects whether the stack is empty. * @return true if the stack is empty */ public boolean isEmpty(); /** Task: Removes all entries from the stack */ public void clear(); } // end StackInterface