Discriminated Unions as Trees

Category:
Defining Types
Description: Discriminated unions are excellent for representing tree structures.
Code:
type Tree<'a> =
| Node of 'a * Tree<'a> * Tree<'a>
| Tip

let UnionSample2() =
let tree = Node(4, Node(2, Node(1, Tip, Tip), Node(6, Tip, Tip)),
Node(6, Node(5, Tip, Tip), Node(7, Tip, Tip)))
// 4
// 2 6
// 1 3 5 7
// InOrder : Tree<'a> -> list<'a>
let rec InOrder t =
match t with
| Node(x,left,right) -> (InOrder left) @ [x] @ (InOrder right)
| Tip -> []

// Height : Tree<'a> -> int
let rec Height t =
match t with
| Node(x,left,right) -> 1 + (max (Height left) (Height right))
| Tip -> 0

printfn "The tree in order = %A" (InOrder tree)
printfn "\nThe height of the tree = %d" (Height tree)


Execution Result:
The tree in order = [1; 2; 6; 4; 5; 6; 7]

The height of the tree = 3

Last edited Sep 14, 2011 at 2:58 AM by ttliu2000, version 1

Comments

No comments yet.