6 people like it.

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