BACK

Binary Expression Tree

 NEXT

PowerPoint Presentation:
Sahni's Lecture 19  discusses arithmetic expressions, postfix and prefix notation, and expression trees:  slides 19–38

Consider the node for a doubly-linked list:

Now, change the links so that they are not horizontal but vertical:

We can now represent a binary expression (such as we encounter in normal arithmetic) as something called a binary expression tree — the links represent parent/child relationships.  For instance, (A+B)*((C-D)/(E^F)) could be represented thus [E^F means E raised to the F power]:

As in the tree-structured directory (which you are familiar with from your computer’s file system), the entry point is called the "root" — in this case, the multiplication.  The link to the left connects to the expression that is the left operand, while the link to the right connects to the expression that is the right operand.  The nodes that have no children (that is, the variables A through F) are referred to as "leaf" nodes.  They will have null references for left and right.  We can now define a way to go through all of the nodes, just as we did for a linked list — something called a tree traversal.  Now, however, we have the problem of needing to go both ways.  As always, recursion is your friend.

The point at which we process the item for a given node will give us different traversals:  if we do it as soon as we start processing the node, we have what is called a "pre-order" traversal.  If we do it after we’ve finished processing both children, we have what is called a "post-order" traversal.  Finally, if we do it between processing the left child and the right child, we have an "in-order" traversal.

If our only action in processing a node is to write out the item, the order of the traversal determines the kind of expression we write out:  a pre-order traversal will write out what is called a prefix expression; a post-order traversal will write out a postfix expression.  The in-order traversal, though, writes out an expression which will not necessarily correspond with the expression (since there are no parentheses).

public void preOrder(TreeNode node)    | public void postOrder(TreeNode node)
{                                      | {
   if ( node != null )                 |    if ( node != null )
   {                                   |    {
      process (node.item);             |       postOrder(node.left);
      preOrder(node.left);             |       postOrder(node.right);
      preOrder(node.right);            |       process  (node.item);
   }                                   |    }
   // Do NOTHING on a null reference   |    // Do NOTHING on a null reference
}                                      | }

(^: You should be able to figure out the method public void inOrder(TreeNode node) yourself. ;^)

 
Do a pre-order traversal on the tree and write out the result.       _________________

 
Do a post-order traversal on the tree and write out the result.       _________________

 
Do an in-order traversal on the tree and write out the result.       _________________

The tree can very easily be generated from the prefix expression:

To generate at tree node (returning the reference to the node)

  1. Generate the node with null references to the left and right.
  2. If the "token" is an operand, just return the reference to the (leaf) node
  3. Otherwise
    1. Recursively generate a tree node and link it as the left subtree
    2. Recursively generate a tree node and link it as the right subtree
    3. Return the reference to the resulting (internal) node

Once you have a binary expression tree, you can do the arithmetic very easily:

To evaluate a node in an expression tree

  1. If the node is a leaf node (an operand), just return the value
  2. Otherwise
    1. Recursively evaluate the left subtree and get its value
    2. Recursively evaluate the right subtree and get its value
    3. Perform the operation indicated by the operator and return THAT value

Given a binary expression tree, you can write the parenthesized infix expression by combining elements of all three traversals:

To write out the expression that starts at this node

  1. If the node is an operator, write the open parenthesis — Pre-order position
  2. If there is a left child node, recursively write the infix expression for that node
  3. Write out the current node's symbol — In-order position
  4. If there is a right child node, recursively write the infix expression for that node
  5. If the node is an operator, write the close parenthesis — Post-order position

Java Code Example — Prefix Expression Calculator

ExpressionTree.java  The expression tree class the contains the TreeNodes objects (link to the same as a text file) — 195 lines
PrefixCalc.java          The prefix calculator that exercises an ExpressionTree object (link to the same as a text file)  — 44 lines
ExpressionTree.rtf      Class hand-out with the above code as two pages of two-column text.   [PDF]

PrefixCalc.jar             Executable jar file [java -jar PrefixCalc.jar] that also includes the above Java source files.
PrefixCalc.exe            The same in a JSmooth .exe wrapper