Mastering Algorithms with C

Binary Tree Example: Expression Processing

One intuitive way to process arithmetic expressions with a computer is using an expression tree. An expression tree is a binary tree consisting of nodes containing two types of objects: operators and terminal values . Operators are objects that have operands; terminal values are objects that have no operands.

The idea behind an expression tree is simple: the subtrees rooted at the children of each node are the operands of the operator stored in the parent (see Figure 9.5). Operands may be terminal values, or they may be other expressions themselves. Expressions are expanded in subtrees; terminal values reside in leaf nodes. One of the nice things about this idea is how easily an expression tree allows us to translate an expression into one of three common representations: prefix, infix, and postfix. To obtain these representations, we simply traverse the tree using a preorder, inorder, or postorder traversal.

Traversing the tree in Figure 9.5 in preorder, for example, yields the prefix expression × / - 74 10 32 + 23 17. To evaluate a prefix expression, we apply each operator to the two operands that immediately follow it. Thus, the prefix expression just given is evaluated as:

( x ( / ( - 74 10 ) 32 ) ( + 23 17 ) ) = 80

Infix expressions are the expressions we are most familiar with from mathematics, but they are not well suited to processing by a computer. If we traverse the tree of Figure 9.5 using an inorder traversal, we get the infix ...