Draw a breadth-first colored binary tree in C#

[binary tree]

The example Draw a colored binary tree in C# shows how to use recursion to draw a colored binary tree. If you look closely at a tree of high degree, however, you’ll notice a problem. The program draws a branch and then recursive draws its left child branch and then its right child branch. From a particular branch, all of the branches down one child are drawn before any branches down the other child. If some of the branches farther down the second child’s path overlap branches that were drawn down the first child’s path, then those branches are drawn on top.



For example, look at the picture on the right. Notice how the “leaves” on the right half of the tree are drawn on top of the branches but many of the “leaves” on the left half of the tree are drawn behind branches.

The problem is that branches are drawn depending on their left-to-right order in the tree instead of on their depth or distance from the root. The solution is to draw the branches in depth-first order with every branch at a particular level drawn before any branch on the next level is drawn.

One way to do that is to make a Stack to hold information about the branches at a particular level. As the program draws the branches in the stack, it stores information about their child branches in a new stack. When it has finished with the first stack, it repeats the process for the new stack to draw all of the child branches.

To store information about branches in stacks, the program needs a class or structure to hold information about a branch. This example uses the following simple BranchInfo class.

// Hold branch information.
private class BranchInfo
{
    public float X, Y, Theta;
    public BranchInfo(float x, float y, float theta)
    {
        X = x;
        Y = y;
        Theta = theta;
    }
}

The BranchInfo class holds the starting X and Y coordinate of a branch and the angle at which it should be drawn. Other information such as its length and color are stored in the following DrawBranch method, which uses stacks to draw the branches.

// Draw a binary tree.
private void DrawBranch(Graphics gr, Pen pen, int depth,
    int max_depth, float x, float y, float length,
    float theta, float length_scale, float dtheta)
{
    // Add the first branch to a stack.
    Stack<BranchInfo> branches =
        new Stack<BranchInfo>();
    branches.Push(new BranchInfo(x, y, theta));

    // Process the branches until we reach the desired depth.
    while (depth > 0)
    {
        // Make a stack for new branches.
        Stack<BranchInfo> new_branches =
            new Stack<BranchInfo>();

        // Set the pen's color depending on the depth.
        if (depth == 1) pen.Color = Color.Red;
        else
        {
            int g = 255 * (max_depth - depth) / max_depth;
            int r = 139 * (depth - 3) / max_depth;
            if (r < 0) r = 0;
            int b = 0;
            pen.Color = Color.FromArgb(r, g, b);
        }

        // Set the pen's thickness depending on the depth.
        int thickness = 10 * depth / max_depth;
        if (thickness < 0) thickness = 0;
        pen.Width = thickness;

        // Process all of the branches in the branches stack.
        while (branches.Count > 0)
        {
            // Get the next branch.
            BranchInfo branch = branches.Pop();

            // See where this branch should end.
            float x1 = (float)(branch.X +
                length * Math.Cos(branch.Theta));
            float y1 = (float)(branch.Y +
                length * Math.Sin(branch.Theta));

            // Draw the branch.
            gr.DrawLine(pen, branch.X, branch.Y, x1, y1);

            // If depth > 1, add the attached
            // branches to the new_branches stack.
            if (depth > 1)
            {
                new_branches.Push(new BranchInfo(x1, y1,
                    branch.Theta + dtheta));
                new_branches.Push(new BranchInfo(x1, y1,
                    branch.Theta - dtheta));
            }
        }

        // Decrement depth so we know how deep
        // into the tree we still need to go.
        depth--;

        // Set the length for the next level of branches.
        length = length * length_scale;

        // Prepare to process the next level of branches.
        branches = new_branches;
    }
}

The picture at the right shows the result.

The DrawBranch method creates a Stack named branches and adds a BranchInfo object to it to represent the tree’s first branch (the trunk). It then enters a while loop that continues as long as the depth is greater than 0.

During each trip through the while loop, the method draws the branches at a particular level, which are represented by the BranchInfo objects in the branches stack. (Initially the stack contains only the tree’s trunk.) The method starts by creating a new stack named new_branches to hold information about the next level of branches.

The method then calculates the color and thickness for the current branches. Because all of the branches it is now drawing have the same level, they all have the same color and thickness.

Next the method processes the branches in the branches stack. While the stack is not empty, it pops the top branch’s information off the stack and draws the branch. If the current depth is greater than 1, it adds information about the branch’s children to the new_branches stack.

After it has drawn all of the branches at the current level, the method decrements the depth and calculates the length for the next level of branches. It sets the branches stack equal to the new_branches stack and repeats the while loop to draw the new branches.

Because this version draws all branches of a given depth before it draws any branches at a greater depth, there’s no problem with branches at different depths overlapping.


Download Example   Follow me on Twitter   RSS feed   Donate




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

4 Responses to Draw a breadth-first colored binary tree in C#

  1. Anonymous says:

    It looks like the download link is broken.

  2. Rod Stephens says:

    It works for me. Give it another try and if it still doesn’t work, email me and I’ll send it to you.

  3. Henk says:

    Dear Rod,
    Would it be possible to update the Draw a breadth-first colored binary tree in C#.
    He does not work properly in Visual Studio 2010.
    I only have 2 lines. And not as nice as the example.
    Especially the color would be nice.
    My thanks and best regards,
    Henk

    • RodStephens says:

      Hi Henk,

      Did you download the example? (Click the Download button at the bottom of the post.)

      It should work in Visual Studio 2010. I don’t have that version installed, but it works in VS 2008 and VS 2013.

      Rod

Leave a Reply

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