RSS Feed
Download our iPhone app
Browse DevX
Sign up for e-mail newsletters from DevX


Taming Trees: Parsing and Sorting : Page 3

Learn how to use parse trees to evaluate mathematical expressions, and how to use sorted trees.

Sorted Trees
A particularly interesting kind of tree keeps its nodes in sorted order. In a binary sorted tree, each node holds a value. To add a new value to the tree, you compare the new value with the root node’s value. If the new value is less than the root’s value, you recursively add the new value to the left child’s subtree. If the value is not less than the root node’s value, you recursively add the new value to the right child’s subtree.

Figure 3. Growing Trees: The new value 3 is added as the left child of node 4.
Eventually, you reach a node that doesn’t have the left or right child into which you would like to move. At that point, you add a new child node, into which you insert the new value.

For example, suppose you want to add the value 3 to the tree on the left in Figure 3. The program starts by asking the root node to compare its value to the new value 3. The value 3 is less than 5 so the program moves into the left child with value 2. The value 3 is greater than 2 so the program moves into node 2’s right child, which has value 4. The new value 4 is less than 4 so the program would move into the node’s left child but, because the node with value 4 has no left child, it creates a new left child and inserts the new value there instead. The result is shown on the right in Figure 3.

The following code shows how the SortedBinaryNode class adds a new value to the tree. The node compares the new value to its current value and then calls the AddValue method of its left or right child as appropriate. If the node doesn’t have the necessary child, it makes one.

' Add a new node to the sorted subtree.
Public Sub AddValue(ByVal value As String)
  ' See if we this value belongs to our right or left.
  If value < Name Then
    ' Go left.
    If LeftChild Is Nothing Then
      LeftChild = New SortedBinaryNode(value)
    End If
    ' Go right.
    If RightChild Is Nothing Then
      RightChild = New SortedBinaryNode(value)
    End If
  End If
End Sub
Figure 4 shows the program in action. As you add new nodes to the tree, the program displays the tree and shows the tree’s inorder traversal. Notice that the inorder traversal of a sorted tree lists the items it contains in sorted order.

Figure 4. All Sorts of Trees: SortedTree builds a sorted tree.

SortedTree uses the SortedBinaryNode class to create sorted trees. The code which accompanies this article contains SortedTree in both Visual Basic and C#.

You can use a similar method to locate items in the tree. To find an item from the root node, compare the node’s value with the target value and move either left or right into the children as appropriate. Eventually, you will either find the node containing the target value, or you’ll reach a point where the child node you need to follow is missing. In the latter case, the item is not in the tree.

An Animal Game
Sorted trees give you a new way to sort a list of items: simply add the items to a sorted tree and then read out the tree’s inorder traversal. While this method works, it’s generally slower than other algorithms designed specifically for sorting lists. However, this type of tree is useful if movement within the tree has some extra meaning.

For example, you can use a sorted tree to build an animal guessing game. Internal nodes store a Yes/No question. Leaf nodes store the name of an animal. When the program visits an internal node, it asks the user the node’s question. If the user answers Yes, the program, moves into the node’s left child. If the user answers No, the program, moves into the node’s right child.

When the program reaches a leaf node, it guesses the animal whose name is stored in that node. If the program is correct, it celebrates. If the guess is wrong, the program asks the user for a new question to add to the tree that will let it tell the difference between whatever the program just guessed and the correct answer. It adds that node to the tree so next time it can tell the animals apart.

Listing 2 shows how the AnimalNode class asks questions. Because this application doesn’t need to draw or traverse the tree, this is a very simple class so the whole thing is shown in Listing 2. AnimalTree uses the AnimalNode class shown in Listing 2. Click here to download both Visual Basic and C# versions and play the animal guessing game.

Complex Trees Equal Powerful Indexing
Parse trees allow you to evaluate mathematical expressions relatively efficiently at run time. You can easily modify the EvaluateExpressions program to support whatever other operators and functions you might require.

Sorted trees also allow you arrange items in sorted order fairly easily. Though the trees in the simple animal guessing game are in some sense toys, they demonstrate some of the principles used to build much more complex trees that can implement powerful indexing features for serious databases

The next tree article will explain B-trees, a type of tree similar to those used by many database management systems to provide indexes.

Rod Stephens is a consultant and author who has written more than a dozen books and two hundred magazine articles, mostly about Visual Basic. During his career he has worked on an eclectic assortment of applications for repair dispatch, fuel tax tracking, professional football training, wastewater treatment, geographic mapping, and ticket sales. His VB Helper web site receives more than 7 million hits per month and provides three newsletters and thousands of tips, tricks, and examples for Visual Basic programmers.
Email AuthorEmail Author
Close Icon
Thanks for your registration, follow us on our social networks to keep up-to-date