he
first part of this series explained basic tree terminology and showed how to build a simple binary tree in Visual Basic
or C#. It also explained how to perform traversals of trees but the only really practical application it showed was how to make a
tree draw itself. That’s pretty handy if you need to display a tree, but trees can do so much more.
This article explains a few more practical uses for trees. First, it explains how to use a tree to parse arithmetic
expressions. It then discusses sorted trees and shows how to use a sorted tree to build a simple animal guessing game.
Evaluating Expressions
You can represent an arithmetic expression such as -2*(8+7)/-10 with an expression tree or
parse tree. Interior nodes in the
tree represent operands such as *, ( ), and /. Leaf nodes represent numbers such as 2, 80, and 3.14159265.
 | |
| Figure 1. Expressive Trees: This tree represents the expression -2*(8+7)/-10. |
The
value of a leaf node is simply the value of its number. To get the value of a non-leaf node, you calculate the values of its children and then combine them by using the appropriate operation.
For example, Figure 1 shows the parse tree for the expression -2*(8+7)/-10. The values of the two lowest nodes are 8 and 7.
The value of their parent node is 8 + 7. If you work through the entire tree, you’ll find that the value of the root node is 3.
Making a parse tree evaluate itself is easy. The node class’s Evaluate function simply calls
its children’s Evaluate function and then combines the results by using the appropriate operand. (More on this later.)
The tricky part is building the parse tree; you need to pick apart the expression and figure out what nodes to
build to represent the expression’s pieces.
The example program EvaluateExpressions, which is available for download in Visual Basic and C#
versions, uses an ExpressionNode class to represent the pieces of an expression. This class uses four variables to
keep track of the sub-expression that it represents. Expression stores a string representing the node’s
sub-expression. LeftChild and RightChild are references to ExpressionNode objects, which represent the node’s children
in the tree. Op holds the node’s operand.
For example, the root node in
Figure 1 has Expression = “-2*(8+7)/-10” and Op = “/”.
The following code shows the ExpressionNode class's constructor. The code saves the node’s expression and sets its children to
Nothing. It then calls the ParseExpression method to do all of the fun work.
' Constructor.
Public Sub New(ByVal new_expression As String)
' Build the expression's parse tree.
Expression = new_expression
LeftChild = Nothing
RightChild = Nothing
ParseExpression()
End Sub
Listing 1 shows the
ParseExpression method.
It’s fairly long and a little tricky, but here’s the general idea.
If you look again at the parse tree shown in Figure 1, you’ll see that the topmost node represents the last operator that
should be applied when evaluating the expression. The node’s children represent the left and right operands for that
operator.
To understand how this works, you first need a little background. The basic idea is to scan through the expression looking
for the operator that should be evaluated last, create child nodes to represent the operands, and then make the children
recursively parse their sub-expressions.
The trickiest part is figuring out which operator should be evaluated last, which is logically the place where you want to break up the expression.
To determine which operator should be evaluated last, the program uses the notion of precedence. An operator’s precedence determines whether it has priority over other operators. For example, normally when you evaluate an expression such as 2+3*4, multiplication has higher precedence than addition, so you perform the multiplication first. That means this expression is equivalent to 2+(3*4).
The ExpressionNode class uses the same precedence rules as Visual Basic and C#. The following table shows operator
precedence in decreasing order. For example, unary + and – have the highest precedence, so they are evaluated first.
| Table 1. Operator precedence: The table shows operator precedence in decreasing order
|
| Operators | Meaning |
| +, - | Unary plus, unary minus |
| ^ | Exponentiation |
| *, / | Multiplication, division |
| \ | Integer division |
| % | Modulus |
| +, - | Addition, subtraction |
