A. Intro
You will continue to use the files from the previous lab.
Stacks and Queues
Two linear data structures that represent objects in the real world are a stack and a queue.
Stack
A stack data structure models a stack of papers, or plates in a restaurant, or boxes in a garage or closet. A new item is placed on the top of the stack, and only the top item on the stack can be accessed at any particular time. Stack operations include the following:
 pushing an item onto the stack;
 accessing the top item of the stack;
 popping the top item off the stack;
 checking if the stack is empty.
Queue
A queue is a waiting line. (The term is more popular in England than it is here.) As with stacks, access to a queue's elements is restricted. Queue operations include:
 adding an item to the back of the queue;
 accessing the item at the front of the queue;
 removing the front item;
 checking if the queue is empty.
B. Working with Stacks and Queues
Exercise 1
Suppose that the following sequence of operations is executed using an initially empty stack. What ends up in the stack?
push A
push B
pop
push C
push D
pop
push E
pop
AC
Exercise 2
Suppose that the following sequence of operations is executed using an initially empty queue. What ends up in the queue?
add A
add B
remove
add C
add D
remove
add E
remove
DE
General Design Concerns for a Tree Iterator
We now consider the problem of returning the elements of a tree one by one, using an iterator. To do this, we will implement the interface java.util.Iterator
.
We will also use a nested iteration class to hide the details of the iteration. As with previous iterators, we need to maintain state saving information that lets us find the next tree element to return, and we now must determine what that information might include. To help work this out, we'll consider the sample tree below, with elements to be returned depth first as indicated by the numbers.
The first element to be returned is the one labeled "1". Once that's done, we have a choice whether to return "2" or "5".
Say we got to "2" next. Once we return element "2", we have a choice between return "3" or "4" next. But don't forget about "5" from eariler!
Say we next return "3" At this point, we still remember that we need to return to "4" and "5" as in the diagram below.
That means that our statesaving information must include not just a single pointer of what to return next, but a whole collection of "bookmarks" to nodes we've passed along the way.
More generally, we will maintain a collection that we'll call fringe or frontier of all the nodes in the tree that are candidates for returning next. The next
method will choose one of the elements of the fringe as the one to return, then add its children to the fringe as candidates for the next element to return. hasNext
is true when the fringe isn't empty.
The iteration sequence will then depend on the order we take nodes out of the fringe. Depthfirst iteration, for example, results from storing the fringe elements in a stack, a lastin firstout structure. The java.util
class library conveniently contains a Stack
class with push
and pop
methods. We illustrate this process on a binary tree in which tree nodes have 0, 1, or 2 children named myLeft
and myRight
. Here is the code.
public class DepthFirstIterator implements Iterator {
private Stack fringe = new Stack();
public DepthFirstIterator() {
if (myRoot != null) {
fringe.push (myRoot);
}
}
public boolean hasNext() {
return !fringe.empty();
}
public Object next() {
if (!hasMoreElements()) {
throw new NoSuchElementException("tree ran out of elements");
}
TreeNode node = (TreeNode) fringe.pop();
if (node.myRight != null) {
fringe.push(node.myRight);
}
if (node.myLeft != null) {
fringe.push(node.myLeft);
}
return node;
}
// We've decided not to use it for this example
public void remove(){
throw new UnsupportedOperationException();
}
}
Stack Contents during DepthFirst Iteration
Exercise 1
What numbers are on the stack when element 4 in the tree below has just been returned by next
?
5
Exercise 2
For the same image above, what numbers are on the stack when element 6 in the tree below has just been returned by next
?
7, 8, 9
Effect of Pushing Left Child Before Right
Suppose the next
code pushes the left child before the right:
if (node.myLeft != null) {
fringe.push(node.myLeft);
}
if (node.myRight != null) {
fringe.push(node.myRight);
}
In what order are the elements of the tree above? Discuss with your partner, then check your answer below.
Answer: 1 5 9 11 10 6 8 7 2 4 3
A DepthFirst Amoeba Iterator
Complete the definition of the AmoebaIterator
class (within the AmoebaFamily
class. It should successively return names of amoebas from the family in preorder, with children amoebas returned oldest first. Thus, for the family set up in the AmoebaFamily
main method, the name "Amos McCoy" should be returned by the first call to next
; the second call to next
should return the name "mom/dad"; and so on. Do not change any of the framework code.
Organizing your code as described in the previous step will result in a process that takes time proportional to the number of amoebas in the tree to return them all. Moreover, the constructor and hasNext
both run in constant time, while next
runs in time proportional to the number of children of the element being returned.
Add some code at the end of the AmoebaFamily
main method to test your solution. It should print names in the same order as the call to family.print
, though without indenting.
A BreadthFirst Amoeba Iterator
Now rewrite the AmoebaIterator
class to use a queue (first in, first out) instead of a stack. (You might want to save your previous code too, though you will be including this version in your submission.) This will result in amoeba names being returned in breadth first order. That is, the name of the root of the family will be returned first, then the names of its children (oldest first), then the names of all their children, and so on. For the family constructed in the AmoebaFamily
main method, your modification will result in the following iteration sequence:
Amos McCoy
mom/dad
auntie
me
Fred
Wilma
Mike
Homer
Marge
Bart
Lisa
Bill
Hilary
You may use either a list (your own List
or the builtin LinkedList
) to simulate a queue, or any subclass of the builtin java.util.Queue
interface.
C. Build and Check a Tree
Printing a Tree
We now return to binary trees, in which each node has either 0, 1, or 2 children. Last lab, we worked with an implementation of binary trees using a BinaryTree class with a nested TreeNode class, as shown below.
public class BinaryTree {
private TreeNode myRoot;
private static class TreeNode {
public Object myItem;
public TreeNode myLeft;
public TreeNode myRight;
public TreeNode (Object obj) {
myItem = obj;
myLeft = myRight = null;
}
public TreeNode (Object obj, TreeNode left, TreeNode right) {
myItem = obj;
myLeft = left;
myRight = right;
}
}
...
}
The framework is available in BinaryTree.java
.
Copy the following code into BinaryTree.java
and fill in the blanks in the following code to print a tree so as to see its structure.
public void print() {
if (myRoot != null) {
myRoot.print(0);
}
}
//In TreeNode
private static final String indent1 = " ";
private void print(int indent) {
// TODO your code here
println (myItem, indent);
// TODO your code here
}
private static void println(Object obj, int indent) {
for (int k=0; k<indent; k++) {
System.out.print(indent1);
}
System.out.println(obj);
}
The print
method should print the tree in such a way that if you turned the printed output 90 degrees clockwise, you see the tree. Here's an example:
Tree
Printed Version
E
C
D
A
B
Checking a BinaryTree
object for validity
First, switch which partner is coding this lab if you haven't already.
A legal binary tree has the property that, when the tree is traversed, no node appears more than once in the traversal. A careful programmer might include a check
method to check that property:
public boolean check() {
alreadySeen = new ArrayList();
try {
isOK(myRoot);
return true;
} catch (IllegalStateException e) {
return false;
}
}
// Contains nodes already seen in the traversal.
private ArrayList alreadySeen;
(IllegalStateException is provided in Java.)
Write and test the isOK
method, using variations of the sample trees you constructed for earlier exercises as test trees. Here's the header:
private void isOK(TreeNode t) throws IllegalStateException;
You may use any traversal method you like. You should pattern your code on earlier tree methods, for example, size
and busiest
.
Incidentally, this exercise illustrates a handy use of exceptions to return from deep in recursion.
Analyzing isOK's running time
Complete the following sentence.
The isOK
method, in the worst case, runs in time proportional to ______
, where N
is ________________
.
Briefly explain your answer to your partner.
N^2
, number of nodes in the tree.
N
is also acceptable if you use a set instead of an arraylist.
Building a Fibonacci Tree
This exercise deals with "Fibonacci trees", trees that represents the recursive call structure of the Fibonacci computation. (The Fibonacci sequence is defined as follows: F0 = 0, F1 = 1, and each subsequent number in the sequence is the sum of the previous two.) The root of a Fibonacci tree should contain the value of the n
th Fibonacci number the left subtree should be the tree representing the computation of the n1
st Fibonacci number, and the right subtree should be the tree representing the computation of the n2
nd Fibonacci number. The first few Fibonacci trees appear below.
Function  Graph 

fibtree(0) 

fibtree(1) 

fibtree(2) 

fibtree(3) 

fibtree(4) 

fibtree(5) 
Supply the fibTreeHelper
method to go with the BinaryTree
method below.
public static BinaryTree fibTree(int n) {
BinaryTree result = new BinaryTree();
result.myRoot = result.fibTreeHelper(n);
return result;
}
private TreeNode fibTreeHelper (int n) ...
Building an Expression Tree
Compilers and interpreters convert string representations of structured data into tree data structures. For instance, they would contain a method that, given a String representation of an expression, returns a tree representing that expression.
Copy the following code into your BinaryTree
class. Complete and test the following helper method for exprTree
.
public static BinaryTree exprTree(String s) {
BinaryTree result = new BinaryTree();
result.myRoot = result.exprTreeHelper(s);
return result;
}
// Return the tree corresponding to the given arithmetic expression.
// The expression is legal, fully parenthesized, contains no blanks,
// and involves only the operations + and *.
private TreeNode exprTreeHelper(String expr) {
if (expr.charAt(0) != '(') {
____; // you fill this in
} else {
// expr is a parenthesized expression.
// Strip off the beginning and ending parentheses,
// find the main operator (an occurrence of + or * not nested
// in parentheses, and construct the two subtrees.
int nesting = 0;
int opPos = 0;
for (int k = 1; k < expr.length()  1; k++) {
// you supply the missing code
}
String opnd1 = expr.substring(1, opPos);
String opnd2 = expr.substring(opPos + 1, expr.length()  1);
String op = expr.substring(opPos, opPos + 1);
System.out.println("expression = " + expr);
System.out.println("operand 1 = " + opnd1);
System.out.println("operator = " + op);
System.out.println("operand 2 = " + opnd2);
System.out.println();
____; // you fill this in
}
}
Given the expression ((a+(5*(a+b)))+(6*5))
, your method should produce a tree that, when printed using the print
method you just designed, would look like
5
*
6
+
b
+
a
*
5
+
a
Optimizing an Expression Tree
Again, switch which partner is coding for this lab if you haven't recently.
Given a tree returned by the exprTree
method, write and test a method named optimize
that replaces all occurrences of an expression involving only integers with the computed value. Here's the header.
public void optimize()
It will call a helper method as did BinaryTree methods in earlier exercises. For example, given the tree produced for
((a+(5*(9+1)))+(6*5))
your optimize method should produce the tree corresponding to the expression
((a+50)+30)
Don't create any new TreeNodes
; merely relink those already in the tree.
D. Conclusion
Readings
The next lab will cover binary search trees.
 JRS: Binary Search Trees
Submission
You will turn in AmoebaFamily.java
, and BinaryTree.java
as lab15. They should still contain all your work from the previous lab.