There are a many ways to write expressions: normal infix notation
using operator precedence and parentheses,
prefix (function) notation, postfix (reverse Polish) notation, and as
trees. Trees are hard to represent in text-based writing
systems, however, they are easy to use in a computer.
In computing diagrams of trees are most often written with the root
at the top.
This example has +, -, and * operators
and integer operands.
Normal infix notation: (7-5) * (3+(1-2))
Tree equivalent:
*
/ \
/ \
- +
/ \ / \
# # # -
7 5 3 / \
# #
1 2
Each node in the tree is represented as a struct/class,
with the following fields:
- The operator, which can be encoded as a char variable.
We'll represent integers with the special operator '#'
and a field that contains the integer value.
- The integer value. This field is always there, but is
only used with the '#' operator.
- A pointer to the the left subtree if it's not the '#' operator
(a terminal node).
- A pointer to the right subtree as above.
Processing trees is made especially easy because it can be done
in a nice, compact, natural, recursive manner.
See the two examples of how to declare this: