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


Taming Trees: Building Branching Structures : Page 3

Learn tree nomenclature and how to build binary trees that can recursively traverse and draw their own nodes.

Taming Trees
Building trees in Visual Studio is pretty easy. First, you make a class to represent a node. This first example builds a binary tree.

Unfortunately the word "Node" is pretty generic (kind of like Object) so it tends to get used in a lot of places. Microsoft has already used the name "Node" in the Microsoft.ManagementConsole, MicrosoftComputeCluster, and Microsoft.TeamFoundation.WorkItemTracking.Client namespaces—and who knows where else. They've also used "TreeNode" in a couple of namespaces so it's hard to pick a completely unambiguous name.

Because this class is the basis for a binary tree, I'll name the class "BinaryNode."

Next, give the class a Name property and two properties that will hold references to the left and right children (also BinaryNodes).

To make building nodes and trees easier, give the class a constructor that initializes the node's name and children:

   Public Class BinaryNode
       Public Name As String
       Public LeftChild As BinaryNode
       Public RightChild As BinaryNode
       ' Constructor.
       Public Sub New(ByVal new_name As String, _
        Optional ByVal left_child As BinaryNode = Nothing, _
        Optional ByVal right_child As BinaryNode = Nothing)
           Name = new_name
           LeftChild = left_child
           RightChild = right_child
       End Sub
That's enough to build the basic tree but not enough to do much with it, so it's worth adding some traversal methods. Listing 1 shows an initial BinaryNode class with preorder, postorder, and inorder functions that return each node's name and its children's names in the proper sequences.

To make using the tree easier, you can build a tree class. Again, to avoid name collisions, call this one "BinaryTree."

Give the tree a public BinaryNode property named Root, and a constructor that initializes the property to a new or specific BinaryNode.

Making the tree produce full traversals is easy. It simply checks whether the root node has been defined and, if so, delegates the call to that node. Note that many tree methods work similarly; in general, they verify the presence of a root node and then let it do all the work.

The following code shows the BinaryTree class:

   Public Class BinaryTree
       Public Root As BinaryNode
       ' Constructor.
       Public Sub New( _
        Optional ByVal new_root As BinaryNode = Nothing)
           Root = new_root
       End Sub
       ' Return the tree's preorder traversal.
       Public Function Preorder() As String
           If Root Is Nothing Then Return ""
           Return Root.Preorder
       End Function
       ' Return the tree's postorder traversal.
       Public Function Postorder() As String
           If Root Is Nothing Then Return ""
           Return Root.Postorder
       End Function
       ' Return the tree's inorder traversal.
       Public Function Inorder() As String
           If Root Is Nothing Then Return ""
           Return Root.Inorder
       End Function
   End Class
All this is pretty interesting but—not to put too delicate a point on the issue—it's not very useful. It's obviously easy to build a tree that can't do much. The rest of this article teaches the tree to do something fairly useful: draw itself.

Close Icon
Thanks for your registration, follow us on our social networks to keep up-to-date