Lab 15: More on Trees

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:

Stack

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:

Queue

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
Toggle Solution

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
Toggle Solution

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.

Tree

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.

Tree

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 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 Depth-First Iteration

Exercise 1

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

Tree

Toggle Solution

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?

Toggle Solution

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.

Toggle Solution

Answer: 1 5 9 11 10 6 8 7 2 4 3

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.

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

Toggle Solution

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 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) Tree
fibtree(1) Tree
fibtree(2) Tree
fibtree(3) Tree
fibtree(4) Tree
fibtree(5) Tree

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.

Submission

You will turn in AmoebaFamily.java, and BinaryTree.java as lab15. They should still contain all your work from the previous lab.