The Java Course provides a general introduction to programming in Java. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.

Trees

Implementing an Abstract Class

If we are using an expression tree to generate infix, then "visiting" a node means printing its contents. Since the contents of an expression tree are tokens, we'll create a new concrete class called Token that implements Visitable

public class Token implements Visitable {
String str;

public Token (String str) {
this.str = str;
}

public void visit () {
System.out.print (str + " ");
}
}

When we compile this class definition (which is in a file named Token.java), the compiler checks whether the methods provided satisfy the requirements specified by the abstract class. If not, it will produce an error message. For example, if we misspell the name of the method that is supposed to be visit, we might get something like, "class Token must be declared abstract. It does not define void visit() from interface Visitable."

The next step is to modify the parser to put Token objects into the tree instead of Strings. Here is a small example:

String expr = "1 2 3 * +";
StringTokenizer st = new StringTokenizer (expr, " +-*/", true);
String token = st.nextToken();
Tree tree = new Tree (new Token (token), null, null));

This code takes the first token in the string and wraps it in a Token object, then puts the Token into a tree node. If the Tree requires the cargo to be Visitable, it will convert the Token to be a Visitable object. When we remove the Visitable from the tree, we will have to cast it back into a Token.

As an exercise, write a version of printPreorder called visitPreorder that traverses the tree and invokes visit on each node in preorder.

Home

Trees

Implementing an Abstract Class

Last Update: 2011-01-24