Wednesday, October 20, 2010

Pre-Order/In-Order/Post-Order tree transversal

when we use the CSP to transverse a tree, I got confused due to the how to implement the pre-order/in-order/post-order transversal.

when i look at previous post, i realize the keypoint is in the highlighted section.

type Tree = 
    E | T of Tree * value * Tree

let rec f2 tree cont =
    match tree with
        | EmptyTree -> cont([])
        | Tree(l, n, r) ->
            f2 l (fun lSum ->
                    f2 r (fun rSum->cont(lSum@[n]@rSum)))

currently it is in-order. You can change it to [n]@lSum@rSum and this will be pre-order.

No comments: