Login | Register   
LinkedIn
Google+
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


advertisement
 

Taming Trees: Building Branching Structures : Page 4

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


advertisement
Drawing Trees
It's not too hard to show a tree's structure by indenting its nodes the way a TreeView control does or the way the left side of Window Explorer does. I'll leave that as an exercise because I'd rather display the tree like the ones shown in Figures 1, 2, and 3.

This is one of those pieces of code that is deceptively short once you figure it out but that can take a while to get right, even if you've seen it before. The goal is to display each node centered above its children. To do that, you first need to figure out where the children will be drawn.

To keep the process as simple as possible, I've broken it into three steps. First, the code recursively traverses the tree, positioning all the nodes. That's the tricky part. Next, the code recursively traverses the tree again, drawing the branches that connect the nodes. Finally, it traverses the tree a third time, drawing the nodes over the branches. The code in Listing 2 shows how the BinaryNode class positions a node and its subtree.

The PositionNode subroutine in Listing 2 takes two parameters, xmin and ymin, which are the minimum X and Y positions where it is allowed to position the tree. Notice that the parameter xmin is passed by reference so changes to its value here will be returned to the calling routine. When this routine finishes, it updates xmin to a value greater than the right edge of the subtree we are positioning now. Any remaining trees at this level will be drawn to the right of the current tree.

The subtree's root node gets placed half the node's radius below ymin, so the code sets the node's m_Cy position accordingly.

Next the code recursively calls the PositionNode method for its left child node. That call recursively draws the entire left subtree and updates xmin to the right edge of that subtree. If this node has two children, you need to leave some room between their subtrees so they don't touch. The code checks and, if the node does have two children, it adds a little space to xmin.

The code then recursively calls the PositionNode method for its right child node. That call recursively draws the entire right subtree and updates xmin to the right edge of that subtree.

At this point, the left and right subtrees have been completely positioned. In particular the left and right child nodes have been positioned so you can use them to figure out the original node's X position. If this node has two children, the code sets its X position to the average of the children's X positions, which centers it. If instead this node has only one child, then the code positions this node directly above its child.

If this node has no children, then the code places this node as far to the left as it can, so its left edge is at xmin. It then increases xmin so that when this call to PositionNode returns, xmin points to this node's right edge.

Simple, right? After that, the rest is easy.

Subroutine DrawBranches, shown in the following code, draws the branches between a node and its children:

' Draw branches to our children. Public Sub DrawBranches(ByVal gr As Graphics, _ ByVal the_pen As Pen) If LeftChild IsNot Nothing Then gr.DrawLine(the_pen, m_Cx, m_Cy, _ LeftChild.m_Cx, LeftChild.m_Cy) LeftChild.DrawBranches(gr, the_pen) End If If RightChild IsNot Nothing Then gr.DrawLine(the_pen, m_Cx, m_Cy, _ RightChild.m_Cx, RightChild.m_Cy) RightChild.DrawBranches(gr, the_pen) End If End Sub

This code checks its left child and, if that child is present, it draws a line connecting the node with that child. It then recursively calls the child's DrawBranches method to make it draw its child branches.

The code then repeats those steps for its right child. (I told you this part was easy.)

Finally, subroutine DrawNode, shown below, draws the node:

' Draw the node in its assigned position. Public Sub DrawNode(ByVal gr As Graphics, ByVal fnt As Font, _ ByVal fill_brush As Brush, ByVal font_brush As Brush, _ ByVal the_pen As Pen) ' Draw an outline. Dim rect As New Rectangle( _ m_Cx - RADIUS \ 2, m_Cy - RADIUS \ 2, RADIUS, RADIUS) gr.FillEllipse(fill_brush, rect) gr.DrawEllipse(the_pen, rect) ' Draw our name. Using sf As New StringFormat() sf.Alignment = StringAlignment.Center sf.LineAlignment = StringAlignment.Center gr.DrawString(Name, fnt, font_brush, m_Cx, m_Cy, sf) End Using ' Draw our children. If LeftChild IsNot Nothing Then LeftChild.DrawNode( _ gr, fnt, fill_brush, font_brush, the_pen) If RightChild IsNot Nothing Then RightChild.DrawNode(_ gr, fnt, fill_brush, font_brush, the_pen) End Sub

This routine first fills an ellipse with a background color at the node's location. It then draws the same ellipse to outline the node. The code then draws the node's name centered at its assigned position.

The routine then recursively calls the DrawNode methods of its children so they can draw themselves.

The following code shows how the BinaryTree class calls the BinaryNode methods to draw the tree. It calls the root node's PositionNode method to recursively position all the nodes. It then calls the root's DrawBranches method to recursively draw all the branches. Finally, it calls the root's DrawNode method to recursively draw all the nodes:



' Draw the tree. Public Sub DrawTree(ByVal gr As Graphics, ByVal fnt As Font, _ ByVal fill_brush As Brush, ByVal font_brush As Brush, _ ByVal the_pen As Pen, ByVal xmin As Integer, _ ByVal ymin As Integer) If Root Is Nothing Then Exit Sub ' Position all the nodes. Root.PositionNode(xmin, ymin) ' Draw all the links. Root.DrawBranches(gr, the_pen) ' Draw all the nodes. Root.DrawNode(gr, fnt, fill_brush, font_brush, the_pen) End Sub

The final piece of code is the form's Paint event handler. It simply calls the tree's DrawTree method, passing it a bunch of drawing parameters:

' Draw the tree. Private Sub Form1_Paint(ByVal sender As Object, _ ByVal e As System.Windows.Forms.PaintEventArgs) Handles Me.Paint m_Tree.DrawTree(e.Graphics, Me.Font, _ Brushes.White, Brushes.Blue, Pens.Black, 10, 100) End Sub

 
Figure 4. Tree Testing: Program BinaryTreeTest demonstrates the BinaryTree and BinaryNode classes.
The example program BinaryTreeTest, which is shown in Figure 4 and available for download in both Visual Basic and C# flavors, demonstrates these methods.

The form's Load event handler uses code to build a tree similar to the one shown in Figure 3. It then uses the tree's methods to display the preorder, postorder, and inorder traversal methods. The form's Paint event handler calls the tree's DrawTree method to display the tree.

Upcoming Trees
Trees are powerful data structures. This article provides a quick introduction to tree terminology and shows how to build binary trees. It also shows how to make relatively simple BinaryNode and BinaryTree classes that can build and draw a tree. But that's not all; in my next tree article, I'll explain how you can use trees to evaluate mathematical expressions. I'll also show how to build and draw trees with higher degrees. Finally, I'll explain B-trees and B+trees—the kinds of trees that databases use to build index structures.



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.
Comment and Contribute

 

 

 

 

 


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

 

 

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