Title: Make a generic TreeNode class in C#, Part 2

This post explains how the TreeNode class uses its generic TreeNode class to arrange and draw a tree. For information about that classes used by this example and how to define the generic TreeNode class it uses, see Make a generic TreeNode class in C#, Part 1.

The program draws the tree in two steps. First it arranges the nodes in the tree and then it draws them. You can do this in a single step, but arranging the nodes requires a separate pass through the tree anyway to figure out where everything goes, so you may as well break the process into two steps to make the code a little easier to understand. That also allows the program to arrange the tree without drawing it, so it can determine how big the tree will be.

Step 1: Arranging Nodes

To TreeNode class's Arrange method shown in the following code arranges the nodes in a TreeNode object's subtree. It takes as a parameter a Graphics object that it can use to measure text. The xmin and ymin parameters give the upper left corner of the area where the subtree is allowed to position itself. When the method returns, it sets xmin and ymin to the lower right corner of the area occupied by the subtree. Its parent node can then use that information to arrange this subtree and its sibling subtrees.

// Arrange the node and its children in the allowed area. // Set xmin to indicate the right edge of our subtree. // Set ymin to indicate the bottom edge of our subtree. public void Arrange(Graphics gr, ref float xmin, ref float ymin) { // See how big this node is. SizeF my_size = Data.GetSize(gr, MyFont); // Recursively arrange our children, // allowing room for this node. float x = xmin; float biggest_ymin = ymin + my_size.Height; float subtree_ymin = ymin + my_size.Height + Voffset; foreach (TreeNode<T> child in Children) { // Arrange this child's subtree. float child_ymin = subtree_ymin; child.Arrange(gr, ref x, ref child_ymin); // See if this increases the biggest ymin value. if (biggest_ymin < child_ymin) biggest_ymin = child_ymin; // Allow room before the next sibling. x += Hoffset; } // Remove the spacing after the last child. if (Children.Count > 0) x -= Hoffset; // See if this node is wider than the subtree under it. float subtree_width = x - xmin; if (my_size.Width > subtree_width) { // Center the subtree under this node. // Make the children rearrange themselves // moved to center their subtrees. x = xmin + (my_size.Width - subtree_width) / 2; foreach (TreeNode<T> child in Children) { // Arrange this child's subtree. child.Arrange(gr, ref x, ref subtree_ymin); // Allow room before the next sibling. x += Hoffset; } // The subtree's width is this node's width. subtree_width = my_size.Width; } // Set this node's center position. Center = new PointF( xmin + subtree_width / 2, ymin + my_size.Height / 2); // Increase xmin to allow room for // the subtree before returning. xmin += subtree_width; // Set the return value for ymin. ymin = biggest_ymin; }

The method starts by calling the GetSize method provided by the TreeNode object's data object. That object returns the amount of space it needs to draw the node. If the TreeNode has no children, then this is the full area needed by the node.

Next the code calls the Arrange method for each of the node's child nodes. After each it adds some horizontal space Hoffset between the children. It also updates the maximum y value needed by any of the children's subtrees.

When it has arranged all of the subtrees, the code checks whether this node itself is wider than the sum of the child subtrees. For example, if this node is displaying the text "A Big Long String" and it has a single child displaying the text "X," then this node is wider than its subtree.

In that case, the code calculates how far to the right it must move the children to center the subtree below this node and then it arranges the children again.

After it has arranged (and possibly rearranged) the subtree nodes, the code sets this node's center point, updates xmin and ymin, and returns.

Step 2: Drawing the Tree

The DrawTree method shown in the following code draws an already arranged tree. It actually uses two steps to draw the links between nodes and then to draw the nodes over the links.

// Draw the subtree rooted at this node. public void DrawTree(Graphics gr) { // Draw the links. DrawSubtreeLinks(gr); // Draw the nodes. DrawSubtreeNodes(gr); }

The DrawSubtreeLinks method draws the tree's links. For each of the node's children, it draws a line between the node and its child, and then recursively calls the child's DrawSubtreeLinks method.

// Draw the links for the subtree rooted at this node. private void DrawSubtreeLinks(Graphics gr) { foreach (TreeNode<T> child in Children) { // Draw the link between this node this child. gr.DrawLine(MyPen, Center, child.Center); // Recursively make the child draw its subtree nodes. child.DrawSubtreeLinks(gr); } }

The DrawSubtreeNodes method draws the tree's nodes. It draws the node and then recursively calls itself to make the node's children draw their nodes.

// Draw the nodes for the subtree rooted at this node. private void DrawSubtreeNodes(Graphics gr) { // Draw this node. Data.Draw(Center.X, Center.Y, gr, MyPen, BgBrush, FontBrush, MyFont); // Recursively make the child draw its subtree nodes. foreach (TreeNode<T> child in Children) { child.DrawSubtreeNodes(gr); } }

My next post will explain how the tree can tell when the user clicks on a node.

Download the example to experiment with it and to see additional details.