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

This example shows how to build a generic TreeNode class that can draw a tree holding just about anything. This is kind of a tricky example, so I'm doing it in two parts. This entry explains the classes and interfaces used. The next entry explains the details of how the TreeNode class arranges and draws a tree.

The example Make a generic priority queue class in C# explains how to make a simple generic class that can hold any type of objects together with priorities. This example builds a more complex class that can draw any type of objects in a tree.

The key class is TreeNode. This class has a Children list that contains references to the node's child nodes in the tree.

The TreeNode class also arranges and draws the subtree rooted at a node. To do that, it must be able to figure out how big a node is and it must be able to draw a node.

But this is a generic class, so it doesn't know what kind of objects it will be drawing for each node. In that case, how can it measure or draw a node's item?

The answer is that the TreeNode class's type parameter has a constraint that requires that type to implement the IDrawable interface. This interface requires that the class provide GetSize and Draw methods. The TreeNode class can then use those methods to draw the subtree.

The following code shows the IDrawable interface.

// Represents something that a TreeNode can draw. interface IDrawable { // Return the object's needed size. SizeF GetSize(Graphics gr, Font font); // Draw the object centered at (x, y). void Draw(float x, float y, Graphics gr, Pen pen, Brush bg_brush, Brush text_brush, Font font); }

The following code shows the TreeNode class declaration plus some of its code.

class TreeNode<T> where T : IDrawable { // The data. public T Data; // Child nodes in the tree. public List<TreeNode<T>> Children = new List<TreeNode<T>>(); ... // Constructor. public TreeNode(T new_data) : this(new_data, new Font("Times New Roman", 12)) { Data = new_data; } public TreeNode(T new_data, Font fg_font) { Data = new_data; MyFont = fg_font; } ... }

The declaration uses a type parameter T. The where clause indicates that T must implement the IDrawable interface. That means the TreeNode class can use an object of Type T's GetSize and Draw methods.

The TreeNode class's Data property is an object of type T. This is the object that the TreeNode will draw. It is of type T so it has GetSize and Draw methods that the TreeNode can use.

The TreeNode class provides two constructors: one that takes a data object as a parameter and one that also includes a font.

This example builds a tree of CircleNode objects. These draw a string inside an ellipse. The following code shows the CircleNode class.

class CircleNode : IDrawable { // The string we will draw. public string Text; // Constructor. public CircleNode(string new_text) { Text = new_text; } // Return the size of the string plus a 10 pixel margin. public SizeF GetSize(Graphics gr, Font font) { return gr.MeasureString(Text, font) + new SizeF(10, 10); } // Draw the object centered at (x, y). void IDrawable.Draw(float x, float y, Graphics gr, Pen pen, Brush bg_brush, Brush text_brush, Font font) { // Fill and draw an ellipse at our location. SizeF my_size = GetSize(gr, font); RectangleF rect = new RectangleF( x - my_size.Width / 2, y - my_size.Height / 2, my_size.Width, my_size.Height); gr.FillEllipse(bg_brush, rect); gr.DrawEllipse(pen, rect); // Draw the text. using (StringFormat string_format = new StringFormat()) { string_format.Alignment = StringAlignment.Center; string_format.LineAlignment = StringAlignment.Center; gr.DrawString(Text, font, text_brush, x, y, string_format); } } }

The class's declaration indicates that CircleNode implements IDrawable. Its Text property holds the string the object will draw.

The GetSize method uses a Graphics object's MeasureString method to see how big the text will be when drawn and then adds a 10 pixel margin.

The Draw method fills and outlines an ellipse around the text, and then draws the text.

When the program starts, the following Form_Load event handler creates the tree.

// The root node. private TreeNode<CircleNode> root = new TreeNode<CircleNode>(new CircleNode("Root")); // Build the tree. private void Form1_Load(object sender, EventArgs e) { TreeNode<CircleNode> a_node = new TreeNode<CircleNode>(new CircleNode("A")); TreeNode<CircleNode> b_node = new TreeNode<CircleNode>(new CircleNode("B")); TreeNode<CircleNode> c_node = new TreeNode<CircleNode>(new CircleNode("C")); TreeNode<CircleNode> d_node = new TreeNode<CircleNode>(new CircleNode("D")); TreeNode<CircleNode> e_node = new TreeNode<CircleNode>(new CircleNode("E")); TreeNode<CircleNode> f_node = new TreeNode<CircleNode>(new CircleNode("F")); TreeNode<CircleNode> g_node = new TreeNode<CircleNode>(new CircleNode("G")); TreeNode<CircleNode> h_node = new TreeNode<CircleNode>(new CircleNode("H")); root.AddChild(a_node); root.AddChild(b_node); a_node.AddChild(c_node); a_node.AddChild(d_node); b_node.AddChild(e_node); b_node.AddChild(f_node); b_node.AddChild(g_node); e_node.AddChild(h_node); // Arrange the tree. ArrangeTree(); }

The code outside the event handler creates the tree's root node. The event handler then creates the other nodes. It uses the nodes' AddChild method to add the nodes to each others' Children lists.

After it has built the tree, the event handler calls the following ArrangeTree method to arrange the tree.

private void ArrangeTree() { using (Graphics gr = this.CreateGraphics()) { // Arrange the tree once to see how big it is. float xmin = 0, ymin = 0; root.Arrange(gr, ref xmin, ref ymin); // Arrange the tree again to center it. xmin = (this.ClientSize.Width - xmin) / 2; ymin = (this.ClientSize.Height - ymin) / 2; root.Arrange(gr, ref xmin, ref ymin); } // Redraw. this.Refresh(); }

The ArrangeTree method creates a Graphics object that it can use to measure text. It then calls the root node's Arrange method to make it arrange its subtree. On input, xmin and ymin indicate the upper left corner of the area in which the tree should be positioned. When the call to Arrange returns, xmin and ymin hold the coordinates of the right and bottom edges of the tree.

The program uses the returned xmin and ymin values to figure out where it must position the tree to center it on the form. It then calls Arrange again to make the root node arrange its subtree centered on the form.

When the forms resizes, the Resize event handler also calls the ArrangeTree to make the tree center itself.

The following code shows the form's Paint event handler.

// Draw the tree. private void Form1_Paint(object sender, PaintEventArgs e) { e.Graphics.SmoothingMode = SmoothingMode.AntiAlias; e.Graphics.TextRenderingHint = TextRenderingHint.AntiAliasGridFit; root.DrawTree(e.Graphics); }

This code simply calls the root node's Draw method. The tree is already arranged, so each node knows where to draw itself.

In my next post, I'll explain the details about how the TreeNode class arranges and draws a subtree.

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