A. Intro

You will continue to use the files from the previous lab. This lab covers the tools and techniques related to traversing the nodes of a tree structure.

B. Building 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. The first technique to traverse trees that we will examine is Depth-first Iteration or Depth-first Search. The general idea is that we walk along each branch, traveling as far down each branch as possible before turning back and examining the next one. We will see that this is actually quite straightforward to implement, both iteratively and recursively.

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 (suppose we break ties by lowest node label). 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 state-saving 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. Depth-first iteration, for example, results from storing the fringe elements in a stack, a last-in first-out 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 left and right. Here is the code.

public class DepthFirstIterator implements Iterator {

    // Where we will store our bookmarks
	private Stack fringe = new Stack();

	public DepthFirstIterator() {
	    if (root != null) {
	        fringe.push (root);
	    }
	}

	// Returns whether or not we have any more "bookmarks" to visit
	public boolean hasNext() {
	    return !fringe.empty();
	}

    /** Throws an exception if we have no more nodes to visit in our traversal. Otherwise,
    it picks the most recent entry to our stack and "explores" it. Exploring it requires 
    visiting the node, adding its children to the fringe, since we must eventually visit
    them too. */
	public Object next() {
	    if (!hasMoreElements()) {
	        throw new NoSuchElementException("tree ran out of elements");
	    }
	    TreeNode node = (TreeNode) fringe.pop();
	    if (node.right != null) {
	        fringe.push(node.right);
	    }
	    if (node.left != null) {
	        fringe.push(node.left);
	    }
	    return node;
	}

    // We've decided not to use it for this example
    public void remove(){
        throw new UnsupportedOperationException();
    }
}

Stack Contents during Depth-First Iteration

For the following exercises, assume that we examine the right child before the left child of a node.

Exercise 1

What numbers are on the stack when element 4 in the tree below has just been returned by next?

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?

Effect of Pushing Left Child Before Right

Suppose the next code pushes the left child before the right:

if (node.left != null) {
	fringe.push(node.left);
}
if (node.right != null) {
	fringe.push(node.right);
}

In what order are the elements of the tree above? Discuss with your partner, then check your answer below.

A Depth-First 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 Breadth-First 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.

The idea behind Breadth-first Search is to explore each level of the tree before exploring the next. Try working out this traversal on paper with the prior exercises to gain intuition for it.

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 root;

    private static class TreeNode {

        public Object item;
        public TreeNode left;
        public TreeNode right;

        public TreeNode (Object obj) {
            item = obj;
            left = right = null;
        }

        public TreeNode (Object obj, TreeNode leftNode, TreeNode rightNode) {
            item = obj;
            left = leftNode;
            right = rightNode;
        }
    }
    ...
}

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 (root != null) {
        root.print(0);
    }
}

//In TreeNode
private static final String indent1 = "    ";

private void print(int indent) {
    // TODO your code here
    println (item, 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(root); 
        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.

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 nth Fibonacci number the left subtree should be the tree representing the computation of the n-1st Fibonacci number, and the right subtree should be the tree representing the computation of the n-2nd 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 static fibTree method that takes in a nonnegative integer n, and returns a Binary Tree that stores the n-th Fibonacci value using the representation above.

public static BinaryTree fibTree(int n) {
    BinaryTree result = new BinaryTree();

}

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. Note: Make sure that all of the items in this tree are Strings (not chars or Integers).

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.root = 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.