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.

25 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.

  10. MMP says:

    Heloo! I’m sorry to bother you, can you post the code for AddChild() method used Form1_Load ? Thank you!

    • RodStephens says:

      It’s no bother! Feel free to ask questions.

      You can always download the example to see how my posts work. This one is fairly complicated so you might want to do that.

      But here’s the AddChild extension method.

      // Add a TreeNode to out Children list.
      public void AddChild(TreeNode<T> child)
      {
          Children.Add(child);
      }

      This simply adds a child node to the tree node’s Children list.

  11. AlexiaM says:

    Hi ! What do you create on Form1.cs[Design]?
    I download your project, but i don’t have that version of Visual Studio and the program doesn’t display anything.
    Thank you!

    • RodStephens says:

      You should be able to load the project into any newer version of Visual Studio. It will upgrade the project to your version. (You can also look in the form designer file to see what controls it is creating, but that’s a lot of work.)

      What version are you using?

      Be sure you unzip the downloaded zip file first. If you don’t unzip it, Visual Studio will pretend that it can open the project but it cannot run it.

      Let me know if you get it working.

      • AlexiaM says:

        Yesss, I solved the problem. Thank you so much!
        I have another question, do you know how should I generate the nodes (numbers from the tree) random? I mean, how to AddChild to the tree random.

        • RodStephens says:

          I’m not sure what you mean. Do you want to build a random tree?

          If you want it completely random, add the nodes to a list in addition to the tree. Then pick a random node from the list to hold the next node.

          • AlexiaM says:

            Yes, that’s what I mean… you can write the code, please? I try something but is not working.

  12. Mustafa BÜKÜLMEZ says:

    Hello!
    This is really good a sample.It worked very well for me. Thank you.
    Can i ask a question?

    What I want is to list employees working under a manager under the manager name.
    So I want to make an organization chart. Can I do this using this example?
    I tried a little bit but couldn’t get the nodes up and down.

    • RodStephens says:

      Yes, this should be fairly easy. Download the example program and change the text displayed in the nodes created when the form loads.

      • Mustafa BÜKÜLMEZ says:

        Sorry, Perhaps i did can’t explain well.
        Every sub node is, a child for upper node. I want make like this…
        Root’s node have 2 child nodes (A, B).
        A’s node have 4 child nodes (AA, AB, AC, AD)
        AB’s node have 25 child nodes.
        If be like this, all 25 child node it stands side by side and overflows the from screen.
        I want all of these 25 child nodes, AB’s node to be under.
        How can i make like this?

        I think it would be better to show it on the image…
        my work
        https://imgur.com/AqurI8k
        I want it to be.
        https://imgur.com/IpVvtCk

        • RodStephens says:

          Yes, the pictures help.

          In the picture that you want, the child nodes are not direct descendants of the parent node. Instead they are descended from each other so they line up vertically.

          Try making Koc Holding a child of Alic1, Dogan Holding a child of Koc Holding, and A 101 Market 1 a child of Dogan Holding. Then it should look like this:

               Alic1
                 |
            Koc Holding
                 |
           Dogan Holding
                 |
          A 101 Market 1

          You may then want to give the CircleNode class a a background brush property so you can give the nodes at a given level the same background color. In your example, gthe child nodes all have a pink background. You can change the class’s constructor to save the color and then make the Draw method use it.

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.