Layout binary tree

Solution to the layout binary tree problem from 99 OCaml problems

Type definition

1: 
2: 
3: 
4: 
5: 
6: 
7:

type 'a binary_tree =
    | Empty
    | Node of 'a * 'a binary_tree * 'a binary_tree

let example_tree =
    Node('a', Node('b', Node('d', Empty, Empty), Node('e', Empty, Empty)),
         Node('c', Empty, Node('f', Node('g', Empty, Empty), Empty)))

Counting leaves

1: 
2: 
3: 
4: 
5:

let rec count_leaves tree =
    match tree with
        | Empty -> 0
        | Node(_,Empty,Empty) -> 1
        | Node(_,a,b) -> (count_leaves a) + (count_leaves  b)

Generating layout

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15:

type 'a pos_binary_tree =
    | E (* represents the empty tree *)
    | N of 'a * int * int * 'a pos_binary_tree * 'a pos_binary_tree 
    (*N(w,x,y,l,r) represents a (non-empty) binary tree with root w "positioned" at (x,y), and subtrees l and r *)

let make_pos_binary_tree  (tree:binary_tree<_>) =
    let rec layout t x depth =
        match t with
            | Empty -> (x,E)
            | Node(a,l,r) ->
                let x',lTree = layout l x (depth+1)
                let x'',rTree = layout r (x'+1) (depth+1)
                (x'',N(a,x',depth,lTree,rTree))
    let finalX,finalTree = layout tree 1 1
    finalTree

Example and rendering

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18:

let laidOutTree = make_pos_binary_tree example_tree

let canvas = Array2D.init 50 50 (fun _ _ -> ' ')

let rec draw tree =
    match tree with
        | E -> ()
        | N(v,x,y,l,r) ->
            canvas.[y,x] <- v
            draw l
            draw r

draw laidOutTree

for y in 0..49 do
    for x in 0..49 do
        stdout.Write(canvas.[y,x])
    stdout.WriteLine()

union case binary_tree.Empty: 'a binary_tree

union case binary_tree.Node: 'a * 'a binary_tree * 'a binary_tree -> 'a binary_tree

type 'a binary_tree =
| Empty
| Node of 'a * 'a binary_tree * 'a binary_tree

Full name: Script.binary_tree<_>

val example_tree : char binary_tree

Full name: Script.example_tree

val count_leaves : tree:'a binary_tree -> int

Full name: Script.count_leaves

val tree : 'a binary_tree

val a : 'a binary_tree

val b : 'a binary_tree

type 'a pos_binary_tree =
| E
| N of 'a * int * int * 'a pos_binary_tree * 'a pos_binary_tree

Full name: Script.pos_binary_tree<_>

union case pos_binary_tree.E: 'a pos_binary_tree

union case pos_binary_tree.N: 'a * int * int * 'a pos_binary_tree * 'a pos_binary_tree -> 'a pos_binary_tree

Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

val make_pos_binary_tree : tree:'a binary_tree -> 'a pos_binary_tree

Full name: Script.make_pos_binary_tree

val layout : ('b binary_tree -> int -> int -> int * 'b pos_binary_tree)

val t : 'b binary_tree

val x : int

val depth : int

val a : 'b

val l : 'b binary_tree

val r : 'b binary_tree

val x' : int

val lTree : 'b pos_binary_tree

val x'' : int

val rTree : 'b pos_binary_tree

val finalX : int

val finalTree : 'a pos_binary_tree

val laidOutTree : char pos_binary_tree

Full name: Script.laidOutTree

val canvas : char [,]

Full name: Script.canvas

module Array2D

from Microsoft.FSharp.Collections

val init : length1:int -> length2:int -> initializer:(int -> int -> 'T) -> 'T [,]

Full name: Microsoft.FSharp.Collections.Array2D.init

val draw : tree:char pos_binary_tree -> unit

Full name: Script.draw

val tree : char pos_binary_tree

val v : char

val y : int

val l : char pos_binary_tree

val r : char pos_binary_tree

val y : int32

val x : int32

val stdout<'T> : System.IO.TextWriter

Full name: Microsoft.FSharp.Core.Operators.stdout

Raw view Test code New version

More information

Link:	http://fssnip.net/lp
Posted:	10 years ago
Author:	Darren Platt, Tomas Petricek
Tags:	binary tree , tree , layout