How to Draw Tree Structure in F#

Today I am discussing how to draw a tree in a F# Windows Forms application. The first thing you need to know is what is a tree. A tree is a collection of nodes or items  that are connected to each other in such a way that no cycle or relationships are allowed. Trees are incredibly useful structures because they allow us to represents hierarchies and compose complex structures and basic parts and simple relationships.

If you want to draw a tree you will define a function drawTree. This function will Take two parameters a graphics object and the tree you want to draw; like below.

let drawTree (g : Graphics) t =

In programming languages trees provide a mechanism for extensibility across many domains and a container to assist us in sorting, searching, compressing and processing data in efficient way.

To implement drawTree first you calculate many constants the function will use like maxWidth  and center. These constants can not be seen by the function outside the drawTree. You can use them in drawTree's inner function without having to pass them around parameters. Like below.

// constants that relate to the size and position of the tree
        let center = g.ClipBounds.Width / 2.0F
        let maxWidth = 32.0F * raise2ToPower (getDepth t)

You will also break the main function into inner function to make the structure of tree easy to understand. Like drawLeaf function to Draw the leaf nodes. Like below.

// function for drawing a leaf node
        let drawLeaf (x : float32) (y : float32) v =
            let value = sprintf "%A" v
            let l = g.MeasureString(value, font)
            g.DrawString(value, font, brush, x - (l.Width / 2.0F), y)

If you want to use connection between nodes than you use connectNodeS method like below.

// draw a connector between the nodes when necessary
        let connectNodes (x : float32) y p =
            match p with
            | Some(px, py) -> g.DrawLine(pen, px, py, x, y)
            | None -> ()

Lastly for final touch you will use drawTreeInner function that is a recursive function which do the real work for drawing the tree like below.

// the main function to walk the tree structure drawing the nodes as we go
let rec drawTreeInner t d w p =
            let x = center - (maxWidth * w)
            let y = d * 32.0F
            connectNodes x y p
            match t with
            | Node (l, r) ->
                g.FillPie(brush, x - 3.0F, y - 3.0F, 7.0F, 7.0F, 0.0F, 360.0F)
                let d = (d + 1.0F)
                drawTreeInner l d (w + (1.0F / d)) (Some(x, y))
                drawTreeInner r d (w - (1.0F / d)) (Some(x, y))
            | Leaf v -> drawLeaf x y v
        drawTreeInner t 0.0F 0.0F None

Getting Started

Step 1: First open a new project in F# using Visual Studio 2010 and give a name to it.

Step 2: Then click on Program.fs file in solution explorer.

Step 3: Write the below code in Program.fs window, your Program.fs window will look like below.

open System
open System.Drawing
open System.Windows.Forms
// The tree type
type 'N Tree =
| Node of 'N Tree * 'N Tree
| Leaf of 'N
// The definition of the tee
let tree =
        Node(
            Node(
                Leaf "C#",
                Node(Leaf "F#", Leaf "WPF")),
            Node(
                Node(Leaf "SILVERLIGHT", Leaf "WINFORM"),
                Leaf "WEBAPP"))
// A function for finding the maximum depth of a tree
let getDepth A =
    let rec getDepthInner A B =
            match A with
            | Node (l, n) ->
                max
                    (getDepthInner l B + 1.0F)
                    (getDepthInner n B + 1.0F)
            | Leaf x -> B
    getDepthInner A 0.0F
// Constants required for drawing the form
let brush = new SolidBrush(Color.Black)
let pen = new Pen(Color.Black)
let font = new Font(FontFamily.GenericSerif, 8.0F)
// a useful function for calculating the maximum number
// of nodes at any given depth
let raise2ToPower (x : float32) =
        Convert.ToSingle(Math.Pow(2.0, Convert.ToDouble(x)))
let drawTree (g : Graphics) t =
// constants that relate to the size and position of the tree
        let center = g.ClipBounds.Width / 2.0F
        let maxWidth = 32.0F * raise2ToPower (getDepth t)
// function for drawing a leaf node
        let drawLeaf (x : float32) (y : float32) v =
            let value = sprintf "%A" v
            let l = g.MeasureString(value, font)
            g.DrawString(value, font, brush, x - (l.Width / 2.0F), y
// draw a connector between the nodes when necessary
        let connectNodes (x : float32) y p =
            match p with
            | Some(px, py) -> g.DrawLine(pen, px, py, x, y)
            | None -> ()
// the main function to walk the tree structure drawing the nodes as we go
        let rec drawTreeInner t d w p =
            let x = center - (maxWidth * w)
            let y = d * 32.0F
            connectNodes x y p
            match t with
            | Node (l, r) ->
                g.FillPie(brush, x - 3.0F, y - 3.0F, 7.0F, 7.0F, 0.0F, 360.0F)
                let d = (d + 1.0F)
                drawTreeInner l d (w + (1.0F / d)) (Some(x, y))
                drawTreeInner r d (w - (1.0F / d)) (Some(x, y))
            | Leaf v -> drawLeaf x y v
        drawTreeInner t 0.0F 0.0F None
// create the form object
let form =
        let temp = new Form(WindowState = FormWindowState.Maximized)
        temp.Resize.Add(fun _ -> temp.Invalidate())
        temp.Paint.Add
            (fun e ->
                e.Graphics.Clip <-
                    new Region(new Rectangle(0, 0, temp.Width, temp.Height))
                drawTree e.Graphics tree)
        temp
Application.Run(form)

Step 4:  Now press F5 to execute the code.

Output

Summary

In this article I have discussed how to draw a Tree in F#.