1 people like it.

concise breadth-first tree traversal

 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: 

type 'a Tree = 
    | Empty 
    | Branch of 'a * 'a Tree * 'a Tree



let tree1 = Branch ('a', Branch ('b', Branch ('d', Empty, Empty),
                               Branch ('e', Empty, Empty)),
                         Branch ('c', Empty,
                               Branch ('f', Branch ('g', Empty, Empty),
                                           Empty))) 



// based on Chris Okasaki's 'Breadth-first numbering: Lessons from a Small
// Exercise in Algorithm Design', translated to f#
// http://www.cs.tufts.edu/~nr/cs257/archive/chris-okasaki/breadth-first.pdf

let rec breadthFirst2 =
    function
    | []                                ->  []
    | Empty::trees                      ->  breadthFirst2 trees
    | Branch (x, left, right) :: trees  ->  x :: breadthFirst2 [yield! trees; yield left; yield right]

let breadthFirst tr = breadthFirst2 [tr]



printfn "%A" (breadthFirst tree1)
union case Tree.Empty: 'a Tree
union case Tree.Branch: 'a * 'a Tree * 'a Tree -> 'a Tree
type 'a Tree =
  | Empty
  | Branch of 'a * 'a Tree * 'a Tree

Full name: Script.Tree<_>
val tree1 : char Tree

Full name: Script.tree1
val breadthFirst2 : _arg1:'a Tree list -> 'a list

Full name: Script.breadthFirst2
val trees : 'a Tree list
val x : 'a
val left : 'a Tree
val right : 'a Tree
val breadthFirst : tr:'a Tree -> 'a list

Full name: Script.breadthFirst
val tr : 'a Tree
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
Raw view Test code New version

More information

Link:http://fssnip.net/tk
Posted:9 years ago
Author:
Tags:

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.