3.6 - Expression Trees
What is an expression tree?
A tree is a data structure that is useful for displaying data that is
organized in a hierarchy. The actual data items are stored in locations called
nodes and the relationships between the data items are represented by
dotted lines called branches.
One example is the Folders tree in Windows Explorer.
Folders within other folders are displayed further to the right in the tree.
Another example is the Table of Contents in the frame just
to the left of what you are presently reading.
Subtopics within other topics are displayed further to the right (indented)
in the tree.
A mathematical expression is also a hierarchy because of
the order of mathematical operations,
so it can also be displayed in a tree. For example the expression:
which is typeset as:
is represented by the tree shown to the right.
The entire expression, a/b*(c+d-e), is contained in the root node of the tree.
It is shown in blue.
This expression contains 3 “factors”, a, b
and (c+d-3), that are either multiplied or divided together.
Therefore 3 branches come out of this node and each of the
factors goes into a node at the end of one of these branches.
The red arrow points to these child nodes.
(These nodes also contain a * or / symbol
to indicate whether this factor is in the numerator or denominator.)
The expression in the third child node, (c+d-e), contains 3 terms, c, d, and e, that
are either added or subtracted together. Therefore 3 branches come out of this
node and each of the terms goes into a node at the end of one of these branches.
The green arrow points to them. (These nodes also contain a + or - symbol
to indicate whether this term is added or subtracted.)
This process of breaking the expression into ever smaller parts, with the
tree growing from left to right, continues until
every branch ends with a node containing either a number or a variable
that represents a number.
When an expression is evaluated, the evaluations travel back through the nodes from
right to left. Every child node must have a value before
its parent node can be evaluated. Here is an example showing how the
expression a b + c d is evaluated with a = 2,
b = 3, c = 4, d = 5.
Follow the sequence of pictures and notice how the numbers
shown in red appear.
Functions are represented as shown in this example:
5 sin (3 x + 2).
The node containing the function (shown in blue) is the root of a brand new tree
that holds the argument of the function. Before the function can be evaluated
this tree must be evaluated.
Exponentials are represented as shown in this example of the expression:
The node containing the exponential (shown in blue) is the root of two new trees,
one that holds the exponent (indicated by the caret symbol, ^, and pointed to
by the red arrow) and one that holds the base. Before the exponential can be evaluated
both of these trees must be evaluated.
What can an expression tree show you?
An expression tree is useful for:
- Understanding the order of operations.
Operations that must be done sooner are further to the right in the tree.
- Counting the number of terms or factors in an expression. Each term or
factor is a child node. For example the expression (a+b)/c+2*d contains
two terms. Hint: You can collapse or
hide a node's children by clicking on the node and then pressing the left arrow
key. You an make the children reappear by pressing the right arrow key.
This picture shows the collapsed view on the left and the expanded view on the right: