BST and DF Traversal

Binary Search Tree and Depth-First Traversal (PreOrder, InOrder, PostOrder)

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51:

module BST_DFRecTraversal

//binary (b) search tree
module btree =
    type Node<'a> = { value : 'a; left : Node<'a> option; right : Node<'a> option }

    let isNull (node : Node<'a> option) = node.IsNone
    let value (node : Node<'a> option) = node.Value.value
    let left (node : Node<'a> option) = node.Value.left
    let right (node : Node<'a> option) = node.Value.right
    let newNode (value, left, right) = Some { value = value; left = left; right = right }

//depth-first (df) recursive traversal
module df_traversal =
    let rec preOrder (node : btree.Node<'a> option, visit : 'a -> unit) =
        if not (btree.isNull(node)) then
            visit (btree.value(node))
            preOrder (btree.left(node), visit)
            preOrder (btree.right(node), visit)

    let rec inOrder (node : btree.Node<'a> option, visit : 'a -> unit) =
        if not (btree.isNull(node)) then
            inOrder (btree.left(node), visit)
            visit (btree.value(node))
            inOrder (btree.right(node), visit)

    let rec postOrder (node : btree.Node<'a> option, visit : 'a -> unit) =
        if not (btree.isNull(node)) then
            postOrder (btree.left(node), visit)
            postOrder (btree.right(node), visit)
            visit (btree.value(node))

let display (title, node : btree.Node<char> option, traversalFun : btree.Node<char> option * (char -> unit) -> unit) =
    printf title
    traversalFun (node, fun x -> printf "%c " x)
    printfn ""

let entryPoint =
    let c = btree.newNode('C', None, None)
    let e = btree.newNode('E', None, None)
    let h = btree.newNode('H', None, None)
    let a = btree.newNode('A', None, None)
    let d = btree.newNode('D', c, e)
    let i = btree.newNode('I', h, None)
    let b = btree.newNode('B', a, d)
    let g = btree.newNode('G', None, i)
    let f = btree.newNode('F', b, g)
    
    display("Pre-order traversal sequence: ", f, df_traversal.preOrder)
    display("In-order traversal sequence: ", f, df_traversal.inOrder)
    display("Post-order traversal sequence: ", f, df_traversal.postOrder)

module BST_DFRecTraversal

type Node<'a> =
  {value: 'a;
   left: Node<'a> option;
   right: Node<'a> option;}

Full name: BST_DFRecTraversal.btree.Node<_>

Node.value: 'a

Node.left: Node<'a> option

type 'T option = Option<'T>

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

Node.right: Node<'a> option

val isNull : node:Node<'a> option -> bool

Full name: BST_DFRecTraversal.btree.isNull

val node : Node<'a> option

property Option.IsNone: bool

val value : node:Node<'a> option -> 'a

Full name: BST_DFRecTraversal.btree.value

property Option.Value: Node<'a>

val left : node:Node<'a> option -> Node<'a> option

Full name: BST_DFRecTraversal.btree.left

val right : node:Node<'a> option -> Node<'a> option

Full name: BST_DFRecTraversal.btree.right

val newNode : value:'a * left:Node<'a> option * right:Node<'a> option -> Node<'a> option

Full name: BST_DFRecTraversal.btree.newNode

val value : 'a

val left : Node<'a> option

val right : Node<'a> option

union case Option.Some: Value: 'T -> Option<'T>

val preOrder : node:btree.Node<'a> option * visit:('a -> unit) -> unit

Full name: BST_DFRecTraversal.df_traversal.preOrder

val node : btree.Node<'a> option

module btree

from BST_DFRecTraversal

val visit : ('a -> unit)

type unit = Unit

Full name: Microsoft.FSharp.Core.unit

val not : value:bool -> bool

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

val isNull : node:btree.Node<'a> option -> bool

Full name: BST_DFRecTraversal.btree.isNull

val value : node:btree.Node<'a> option -> 'a

Full name: BST_DFRecTraversal.btree.value

val left : node:btree.Node<'a> option -> btree.Node<'a> option

Full name: BST_DFRecTraversal.btree.left

val right : node:btree.Node<'a> option -> btree.Node<'a> option

Full name: BST_DFRecTraversal.btree.right

val inOrder : node:btree.Node<'a> option * visit:('a -> unit) -> unit

Full name: BST_DFRecTraversal.df_traversal.inOrder

val postOrder : node:btree.Node<'a> option * visit:('a -> unit) -> unit

Full name: BST_DFRecTraversal.df_traversal.postOrder

val display : title:Printf.TextWriterFormat<unit> * node:btree.Node<char> option * traversalFun:(btree.Node<char> option * (char -> unit) -> unit) -> unit

Full name: BST_DFRecTraversal.display

val title : Printf.TextWriterFormat<unit>

val node : btree.Node<char> option

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

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

--------------------
type char = System.Char

Full name: Microsoft.FSharp.Core.char

val traversalFun : (btree.Node<char> option * (char -> unit) -> unit)

val printf : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printf

val x : char

val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn

val entryPoint : unit

Full name: BST_DFRecTraversal.entryPoint

val c : btree.Node<char> option

val newNode : value:'a * left:btree.Node<'a> option * right:btree.Node<'a> option -> btree.Node<'a> option

Full name: BST_DFRecTraversal.btree.newNode

union case Option.None: Option<'T>

val e : btree.Node<char> option

val h : btree.Node<char> option

val a : btree.Node<char> option

val d : btree.Node<char> option

val i : btree.Node<char> option

val b : btree.Node<char> option

val g : btree.Node<char> option

val f : btree.Node<char> option

module df_traversal

from BST_DFRecTraversal

Raw view Test code New version

More information

Link:	http://fssnip.net/jG
Posted:	11 years ago
Author:	Fabio Galuppo
Tags:	trees , algorithms