[C# Helper]
Index Books FAQ Contact About Rod
[Essential Algorithms, Second Edition]

[The Modern C# Challenge]

[WPF 3d, Three-Dimensional Graphics with WPF and C#]

[The C# Helper Top 100]

[Interview Puzzles Dissected]

[C# 24-Hour Trainer]

[Beginning Software Engineering]

[C# 5.0 Programmer's Reference]

[MCSD Certification Toolkit (Exam 70-483): Programming in C#]

Title: Recursively draw a binary tree in C#

[Recursively draw a binary tree in C#]

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 the example to experiment with it and to see additional details.

© 2009-2022 Rocky Mountain Computer Consulting, Inc. All rights reserved.