Login | Register   
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.

Comment and Contribute






(Maximum characters: 1200). You have 1200 characters left.



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