3 people like it.

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