[Camllist] tree walking with... specular rec functions? what else?
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20030509 (15:12) 
From:  Brian Hurt <brian.hurt@q...> 
Subject:  Re: [Camllist] tree walking with... specular rec functions? what else? 
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 depthfirst 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 nonleaf 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 5generation grandchildren only? A variant of the breadthfirst 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 camllistrequest@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners