Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
Algebraic expressions such as
have an inherent tree-like structure.
For example,
Figure 
is a representation
of the expression in Equation .
This kind of tree is called
an expression tree .
The terminal nodes (leaves) of an expression tree are the variables
or constants in the expression (a, b, c, d, and e).
The non-terminal nodes of an expression tree are the operators
(+, -, 
, and 
).
Notice that the parentheses which appear in Equation
do not appear in the tree.
Nevertheless, the tree representation has captured the intent of the
parentheses since the subtraction is lower in the tree than the multiplication.
Figure: Tree representing the expression a/b+(c-d)e
The common algebraic operators are either unary or binary. E.g., addition, subtraction, multiplication and division are all binary operations and negation is a unary operation. Therefore, the non-terminal nodes of the corresponding expression trees have either one or two non-empty subtrees. I.e., expression trees are usually binary trees.
What can we do with an expression tree?
Perhaps the simplest thing to do is
to print the expression represented by the tree.
Notice that an inorder traversal of the tree in Figure
visits the nodes in the order
Except for the missing parentheses,
this is precisely the order in which the symbols appear
in Equation !
This suggests that an inorder traversal should be used to print the expression. Consider an inorder traversal which, when it encounters a terminal node simply prints it out; and when it encounters a non-terminal node, does the following:
we get
which, despite the redundant parentheses,
represents exactly the same expression as Equation .
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.
