Re: [Caml-list] tree walking with... specular rec functions? what else?

[Brian Hurt <brian.hurt@qlogic.com>]

On Fri, 9 May 2003, Stalkern 2 wrote:

> Hello to everybody 
> 
> I've a simple tree structure and I want to walk it. Since in such a simple  
> tree structure I can go AFAIK only sidewards or upwards/downwards, and I need 
> to do both, I guess what can be an efficent way to do so.

Recursion is your friend.  Let's assume we have a type like:

type 'a tree = Leaf
             | Node of 'a * 'a tree * 'a tree

This is the most basic of tree data structures.  Data can be held in any 
node, the bottom of the tree is marked by leafs.  We want to define a walk 
function, which calls a function f on all elements of the tree, in a 
depth-first pattern.  This is simple:

let rec walk f tree =
    match tree with
        Leaf -> ()
        | Node(data, left, right) ->
            walk f left;
            f data;
            walk f right
;;

Obvious variations include which order you evaluate the last three 
statements as.  Equally valid would be: f data; walk f left; walk f right;
and walk f left; walk f right; f data; .

Doing a breadth first is a little bit more tricky, as you have to keep a 
list of the next nodes down:

let rec walk f tree =
    let rec inner lst accum =
        match lst with
            [] -> List.rev accum
            | Leaf :: t -> inner t accum
            | Node(data, left, right) :: t -> 
                f data;
                inner t (right :: left :: accum)
    in
    let rec outer lst =
        if (List.length lst) == 0 then ()
        else outer (inner lst [])
    in
    outer ( [ tree ] )
;;

Basically, I keep a list of the nodes at each level.  As I walk the list,
calling f on all non-leaf nodes, I create the list of the nodes at the
next level down.  Note the List.rev trick I pull, to keep the nodes in the
"expected" order.  

> 	2) I think that this approach isn't flexible. What if I had a
> tree where I can move in other directions as well? Or if I were
> dealing with 5-generation grandchildren only?

A variant of the breadth-first walking I did above could easily generate a
list of all nodes on level 5.  Dealing with multiple children is easy.  
Assume that instead of the binary tree structure we had above, we had an 
n'ary tree structure, like:

type 'a tree = Leaf
             | Node of 'a * 'a tree list

Each node holds data and a list of 0 or more children it has.  Depth first 
search would then become:

let rec walk f tree =
    let rec loop lst =
        match lst with
            [] -> ()
            | h :: t -> walk f h ; loop t
    in
    match tree with
        Leaf -> ()
        | Node(data, children) ->
            f data;
            loop children
;;

A similiar modification works to do breadth first walking.  More general
data structures aren't really trees anymore, they're graphs.  But graph
walking works more or less the same way.

Hope this helps.

Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners