Recursively draw a binary tree in C#

[example]

This example shows how you can use recursion to draw a binary tree. Recursion occurs when a method calls itself. It may call itself directly (simple recursion) or indirectly by calling another method that calls the first (indirect recursion). It may also call itself multiple times as in this example (multiple recursion).

In all cases, the method must have some sort of stopping condition to prevent it from recursing forever. In this example and many others, the recursive method takes a depth parameter. In each recursive call to the method, depth is reduced by 1. When depth reaches 1 (or in some programs 0), the recursive method does not call itself so the recursion stops.

The following code shows this example’s recursive DrawBranch method. This method draws a single branch in the tree in a given direction and with a certain length.

// Recursively draw a binary tree branch.
private void DrawBranch(Graphics gr, Pen pen, int depth,
    float x, float y, float length, float theta,
    float length_scale, float dtheta)
{
    // See where this branch should end.
    float x1 = (float)(x + length * Math.Cos(theta));
    float y1 = (float)(y + length * Math.Sin(theta));

    gr.DrawLine(pen, x, y, x1, y1);

    // If depth > 1, draw the attached branches.
    if (depth > 1)
    {
        DrawBranch(gr, pen, depth - 1, x1, y1,
            length * length_scale, theta + dtheta, length_scale,
            dtheta);
        DrawBranch(gr, pen, depth - 1, x1, y1,
            length * length_scale, theta - dtheta, length_scale,
            dtheta);
    }
}

The method first draws its own branch. Then if depth is greater than 1, the method recursively calls itself to draw two new branches turned by angles dtheta and -dtheta from the current branch. The new branches’ lengths are the length of the current branch times length_scale so branches get shorter as you move out from the tree’s trunk. (Although you can set length_scale > 1 for some interesting effects.)

By experimenting with the program’s parameters, you can get some interesting results. For example, try Depth = 13 and DTheta = 60. One warning, however. The program draws 2depth – 1 lines so the number of lines grows very quickly as depth increases. Don’t try very large depths (for example 50) until you know how fast your computer is.


Download Example   Follow me on Twitter   RSS feed   Donate




This entry was posted in algorithms, drawing, fractals, graphics and tagged , , , , , , , , , , , , , , . Bookmark the permalink.

10 Responses to Recursively draw a binary tree in C#

  1. Eddie Bole says:

    A nice fractal tree. Would it be possible to have the branches alternating with different colours?

  2. Rod Stephens says:

    Sure. You would just need to keep track of the color you’re using and then move to a new color on a new branch.

    I’m not sure exactly what you’re looking for here. For example, if you have alternate branches side-by-side use different colors, you’d basically have all left branches one color and all right branches another.

    Or you could give each branch a random color.

    Or you could give all branches at a given level the same color so the colors change the farther up the tree you go. I’ll post an example that demonstrates that approach in a couple days (after I finish the current discussion of anonymous methods and lambda statements).

    (If you want to see one of the other approaches, let me know and I’ll post that, too.)

  3. Eddie Bole says:

    Thanks Rod for your reply. I didn’t realize that you replied to my initial reply. I tried the link “Draw a colored binary tree in C#.” provided, but the page does not load. Yes that is what I wanted “colors change the farther up the tree you go”. I saw something like this in VB6 on a French site, which looked cool. Also how could you save the picture to a file? I hope not to bother you too much Rod.

  4. Eddie Bole says:

    “Only a couple thousand to go”. Many apologies for the help and sorry about the hassles. Regards Edd.

    • RodStephens says:

      No problem. It’s just going to take a while to get through them all 😉

      I’m just sorry people need to put up with the broken links and poorly formatted code in the mean time. The code still (mostly) works, though.

  5. Pingback: Draw a colored binary tree in C# - C# HelperC# Helper

  6. Pingback: Use Stacks to solve the Tower of Hanoi problem in C#C# Helper

  7. Pingback: Recursively solve the Tower of Hanoi problem in C#C# Helper

Leave a Reply

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