Java Reference
In-Depth Information
ȗ Visit the right subtree
ȗ Visit the root
These two visitation schemes will not print the tree in sorted order. However, they are
important in other applications of binary trees. Here is an example.
732
733
Figure 14
Expression Trees
In
Chapter 13
, we presented an algorithm for parsing arithmetic expressions such as
(3 + 4) * 5
3 + 4 * 5
It is customary to draw these expressions in tree formȌsee
Figure 14
. If all operators
have two arguments, then the resulting tree is a binary tree. Its leaves store numbers,
and its interior nodes store operators.
Note that the expression trees describe the order in which the operators are applied.
This order becomes visible when applying the postorder traversal of the expression
tree. The first tree yields
3 4 + 5 *
whereas the second tree yields
3 4 5 * +
