# C++ Notes: Expression Trees

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:

- Expression Tree Struct
- Expression Tree Class - 1