Tree Implementations - Data Structures and Abstractions with Java - page 615

Programming Tip: An iterator object that has not traversed the entire binary tree can be
adversely affected by changes to the tree.

Note: A complete traversal of an n -node binary tree is an O( n ) operation, if visiting a node
is O(1), for both recursive and iterative implementations.

An Implementation of an Expression Tree

24.17

In the previous chapter, you saw that an expression tree is a binary tree that represents an algebraic
expression. Figure 23-14 provided some examples of these trees. By using the algorithm given in
Segment 23.22, we can evaluate the expression in this type of tree.
We can define an interface for an expression tree by extending the interface for a binary tree and
adding a declaration for the method evaluate , as shown in Listing 24-4. Since you can treat the com-
ponents of an expression as strings, we assume that an expression tree contains strings as its data.

LISTING 24-5

An interface for an expression tree

package TreePackage;
public interface ExpressionTreeInterface
extends BinaryTreeInterface<String>

{

/** Computes the value of the expression in this tree.
@return the value of the expression */
public double evaluate();
} // end ExpressionTreeInterface

24.18

An expression tree is a binary tree, so we can derive a class of expression trees from BinaryTree . We
implement the method evaluate as a part of the derived class. A portion of the class ExpressionTree
appears in Listing 24-5.

LISTING 24-6

The class ExpressionTree

package TreePackage;
public class ExpressionTree extends BinaryTree<String>
implements ExpressionTreeInterface

{

public ExpressionTree()
{
} // end default constructor

public double evaluate()
{

return evaluate(getRootNode());
} // end evaluate