Trees - Data Structures and Abstractions with Java - page 580

A postorder traversal of an expression tree visits the root's left subtree, then the root's right
subtree, and finally the root. If during the visits to the subtrees we evaluate their expressions, we
can combine the results with the operator in the root and get the value of the original expression.
Thus, the value of an expression tree is given by the following recursive algorithm:
Algorithm evaluate(expressionTree)
if (expressionTree is empty)
return 0
else
{

firstOperand = evaluate( left subtree of expressionTree)
secondOperand = evaluate( right subtree of expressionTree)
operator = the root of expressionTree
return the result of the operation operator and its operands firstOperand
and secondOperand

}
We will implement an expression tree in the next chapter.

Question 12 What value does the previous algorithm return for the expression tree in
Figure 23-14b? Assume that a is 3, b is 4, and c is 5.

Decision Trees

23.23

Example: Expert systems. An expert system helps its users solve problems or make decisions.
Such a program might help you pick a major or apply for financial aid. It reaches a conclusion
based upon your answers to a series of questions.
A decision tree can be the basis of an expert system. Each parent (nonleaf) in a decision tree is
a question that has a finite number of responses. For example, we might use questions whose
answers are true or false, yes or no, or multiple choice. Each possible answer to the question corre-
sponds to a child of that node. Each child might be an additional question or a conclusion. Nodes
that are conclusions would have no children, and so they would be leaves.
In general, a decision tree is an n -ary tree so that it can accommodate multiple-choice questions.
Often, however, a decision tree is a binary tree. For example, the decision tree in Figure 23-15 shows
part of a binary tree of yes-or-no questions that diagnose a problem with a television. To use this
decision tree, we first would display the question in the root. According to the user's answer, we
would move to the appropriate child and display its contents. Thus, we move along a path in a deci-
sion tree from the root to a leaf according to responses made by the user. At each nonleaf, we display
a question. When we reach a leaf, we provide a conclusion. Notice that each node in a binary deci-
sion tree either has two children or is a leaf.
A decision tree provides operations that move us along a path through the tree and access the
current node. Listing 23-4 contains a possible Java interface for a binary decision tree.

LISTING 23-4

An interface for a binary decision tree

package TreePackage;
public interface DecisionTreeInterface<T> extends BinaryTreeInterface<T>
{

/** Gets the data in the current node.
@return the data object in the current node, or
null if the current node is null */
public T getCurrentData();