Use a queue to draw a breadth-first colored binary tree in C#

[binary tree]

The example Draw a breadth-first colored binary tree in C# shows how to use a Stack to draw a binary tree in depth-first order. The program builds a Stack representing the bottom (trunk) level of the tree. For each level, it processes the Stack, adding child branches for the next level to a new Stack.

This example shows how you can use a Queue to implement a slightly simpler approach. The following code shows the BranchInfo class that the program uses to hold information about a branch that it will later draw.

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

This object holds a branch’s starting position, direction, length, and depth in the tree.

The following code shows how the program draws its tree.

// Draw a binary tree.
private void DrawTree(Graphics gr, Pen pen,
    int max_depth, float x, float y, float max_length,
    float initial_theta, float length_scale, float dtheta)
{
    // Add the trunk to a queue.
    Queue<BranchInfo> branches = new Queue<BranchInfo>();
    branches.Enqueue(new BranchInfo(x, y, initial_theta,
        max_length, max_depth));

    // Process branches until the queue is empty.
    while (branches.Count > 0)
    {
        // Draw the next branch.
        BranchInfo branch = branches.Dequeue();

        // Set the pen's color depending on the depth.
        if (branch.Depth == 1) pen.Color = Color.Red;
        else
        {
            int g = 255 * (max_depth - branch.Depth) / max_depth;
            int r = 139 * (branch.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 * branch.Depth / max_depth;
        if (thickness < 0) thickness = 0;
        pen.Width = thickness;

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

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

        // If branch.depth > 1, add child branches to the queue.
        if (branch.Depth > 1)
        {
            branches.Enqueue(new BranchInfo(x1, y1,
                branch.Theta + dtheta,
                branch.Length * length_scale,
                branch.Depth - 1));
            branches.Enqueue(new BranchInfo(x1, y1,
                branch.Theta - dtheta,
                branch.Length * length_scale,
                branch.Depth - 1));
        }
    }
}

The method starts by creating a Queue and adding a new BranchInfo object to it to represent the tree’s trunk. It then enters a while loop that executes as long as the Queue isn’t empty.

Inside the loop, the code calls the Queue‘s Dequeue method to get the next item from the queue. In a Queue, items are added and removed in first-in-first-out or FIFO order. That means the Dequeue method returns the item that has been in the queue the longest. (This is the way a line (or queue if you’re British) works when you’re waiting for the bus.)

The program draws the branch that was just removed from the Queue. Then if the branch’s depth is greater than 1, the code adds the branch’s children to the Queue.

The program repeats the while loop until the Queue is empty.

Inside the Queue, all of the branches of a given depth are grouped together. To see why, consider that initially the trunk is the only branch and suppose it has depth 10.

When the program processes the trunk, it adds two branches of depth 9. They are the only branches in the Queue, so they are grouped together.

Next the program processes the two depth 9 branches and adds their children to the end of the Queue. Because they go at the end and the existing branches are at the front of the Queue, the depth 8 children are grouped together at the end.

More generally, suppose the program has removed all of the branches of depth D and the Queue contains only branches of depth D – 1. They are all at the front of the Queue. As it processes those branches, the code adds branches at depth D – 2 to the end of the Queue. They all come after the depth D – 1 branches, so they are grouped, too.

Eventually the Queue contains branches of depth 1. When the program processes them, it doesn’t add child branches to the Queue so the Queue empties out and the loop ends.


Download Example   Follow me on Twitter   RSS feed   Donate




About RodStephens

Rod Stephens is a software consultant and author who has written more than 30 books and 250 magazine articles covering C#, Visual Basic, Visual Basic for Applications, Delphi, and Java.

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

Leave a Reply

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