Make a generic TreeNode class in C#, Part 1

[generic TreeNode class]

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 Example   Follow me on Twitter   RSS feed   Donate




This entry was posted in classes, generic, OOP and tagged , , , , , , , , , , . Bookmark the permalink.

14 Responses to Make a generic TreeNode class in C#, Part 1

  1. Richard Moss says:

    Nice sample, I actually had started trying to do something similar for displaying a diagram of a website layout – I think your example is going to be of good use in working it out 🙂

    I did manage to crash the sample by adding E as a child of H which caused a stack overflow due to the circular relationship 😉

    Regards;
    Richard Moss

  2. Rod Stephens says:

    Yeah, many of the examples are not bullet proof. Adding full error handling sometimes obscures the main ideas. (Besides, I’m lazy 😉

    But I’m glad you found the example useful.

  3. CodeWarrior says:

    Wow! Great stuff! Next step for me is to be able to add new nodes at runtime by clicking on any node…however i get the feeling that it is going to be complicated. Maybe i should try drawing a tree of all directories on my hard disk first…

  4. Rod Stephens says:

    I think that’s doable. After I post Part 2 (today, I think), I’ll show how to learn when a node has been clicked. It shouldn’t be too bad.

  5. einherjar says:

    Really great article, the commenting in the code is super!

  6. Pingback: Make a generic TreeNode class in C#, Part 2 - C# HelperC# Helper

  7. Pingback: Draw a tree with nodes containing pictures in C# - C# HelperC# Helper

  8. NAMANE SARA says:

    the example is verry useful but i have a question can i add a weights to the tree , i have values introduced by users in datagridview i have the algorithm of creating a tree but to draw it with weights i don’t find solution.

  9. Martin says:

    Simple and good to follow. Thanks Rod!

    I would like to extend the tree to this:

    http://pre14.deviantart.net/2b3e/th/pre/f/2015/287/8/0/family_tree_by_cybzilla-d9d4noq.png

    So each TreeNode could have 0..* Spouses. How to generate/modify the classes to get this one?

    • RodStephens says:

      At this point you don’t have a simple tree any more. If you have 0 or 1 spouses, you can probably modify the example to work in some sense. You would need to allow extra room for the spouse if present and then put the child tree below the = sign between the two parents.

      If you want to allow more than 1 spouse, things get tricky. I don’t know how ancestry tools handle that. You could move new trees off to the side and connect them with dashed lines or something. Or you could use a root symbol that included images of both parents.

      At some point it may be easier to just make the program a CAD tool and let the user assist in the layout.

Leave a Reply

Your email address will not be published. Required fields are marked *