Java Reference
In-Depth Information
FIGURE 23-14
Expression trees for four algebraic expressions
(a)
a
/
b
(b)
a
*
b
c
(c)
a
*
(
b
c
)
(d)
a
*
(
b
c
*
d
)
/
e
/
/
*
a
b
c
a
e
*
*
a
b
c
a
b
b
*
c
d
23.21
Segment 5.5 mentioned that we can write an algebraic expression in several ways. The expressions
that we normally write, in which each binary operator appears between its two operands, are called
infix expressions. A prefix expression places each operator before its two operands, and a postfix
expression places each operator after its two operands. Various traversals of an expression tree are
related to these forms of an expression.
An inorder traversal of an expression tree visits the variables and operators in the tree in the
order in which they appear in the original infix expression. If we were to write each node's contents
when we visited it, we would get the infix expression, but without any parentheses.
A preorder traversal produces a prefix expression that is equivalent to the original infix expression.
For example, a preorder traversal of the tree in Figure 23-14b visits nodes in this order:
+
*
a b c
.
This result is the prefix form of the infix expression
a
*
b
+
c
. Recall that, like an expression tree, a
prefix expression never contains parentheses.
A postorder traversal produces a postfix expression that is equivalent to the original expression.
A postfix expression also has no parentheses, so the traversal produces the correct result. For exam-
ple, a postorder traversal of the tree in Figure 23-14b visits nodes in the following order:
a b
*
c
+
.
This result is the postfix form of the infix expression
a
*
b
+
c
.
Question 9
Write an expression tree for each of these algebraic expressions.
a.
a
+
b
*
c
b.
(
a
+
b
)
*
c
Question 10
In what order are nodes visited by a preorder, inorder, and postorder traversal
of the trees in Parts
a
,
c
, and
d
of Figure 23-14?
Question 11
Which trees, if any, in Figure 23-14 are full? Which are complete?
23.22
Evaluating an algebraic expression.
Since an expression tree represents the order of an expres-
sion's operations, we can use it to evaluate the expression. The root of an expression tree is always
an operator whose operands are represented by the root's left and right subtrees. If we can evaluate
the subexpressions that these subtrees represent, we can evaluate the entire expression. Notice that
such is the case for each expression tree in Figure 23-14, if we know the values of the variables.
