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)
Once you have a binary expression tree, you can do the arithmetic very easily:
To evaluate a node in an expression tree
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
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