A tree is a natural way to represent the structure of an expression. Unlike other notations, it can represent the computation unambiguously. For example, the infix expression 1 + 2 * 3 is ambiguous unless we know that the multiplication happens before the addition.
This expression tree represents the same computation:
The nodes of an expression tree can be operands like 1 and 2 or operators like + and *. Operands are leaf nodes; operator nodes contain references to their operands. (All of these operators are binary, meaning they have exactly two operands.)
We can build this tree like this:
>>> tree = Tree('+', Tree(1), Tree('*', Tree(2), Tree(3)))
Looking at the figure, there is no question what the order of operations is; the multiplication happens first in order to compute the second operand of the addition.
Expression Tree to Different Notations
Consider the above Tree, we can see different notations based on different traversals.
For eg. inorder traversal results in infix notation; Likewise postorder results in postfix notations
>>> tree = Tree('+', Tree(1), Tree('*', Tree(2), Tree(3)))
>>> preorder(tree) # prefix
+ 1 * 2 3
>>> postorder(tree) # postfix
1 2 3 * +
>>> inorder(tree) # infix
1 + 2 * 3
To be fair, we should point out that we have omitted an important complication. Sometimes when we write an expression in infix, we have to use parentheses to preserve the order of operations. So an inorder traversal is not quite sufficient to generate an infix expression.
Applications
Expression trees have many uses. The example in this chapter uses trees to translate expressions to postfix, prefix, and infix. Similar trees are used inside compilers to parse, optimize, and translate programs.