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. For example, 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. That is, 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:
which, despite the redundant parentheses, represents exactly the same expression as Equation .