Walking Trees Backwards

David Bovill david at architex.tv
Thu Sep 11 10:43:55 EDT 2008


No before anyone asks this isn't a new age thing :) It's about hierarchical
(tree) data structures - not being a computer scientist its out of my
league, and I feel that someone who knows a bit about these beasts can
advise.

*Task*
I want to put an indented outline (more generally a tree structure) into an
array.

*Background*
An outline is your regular tab indented outline you might have in a word
processor or a rev field. I have a small library for these structures as I
have to deal with them a lot - so I can turn them into XML and use paths
(nodes) and get children and parent relationships etc. Quite a lot of them
are recursive.

*Problem*
With XML I could add the bits as I walked down the tree. I think I can do
the same with the new array structures in 3.0 - but for compatibility I was
thinking of using a technique for marshaling arrays - that allows arrays to
be arbitrarily nested - but for that I need to walk the trees backwards from
leaf to trunk. This is getting complicated - I dislike recursion at the best
of times - but backwards recursion with marshaling doesn't not sound good :)

I am thinking of something roughly along the lines of:

   1. working out the maximum depth of the outline and then repeating
*down*from that
   2. for each node finding its parent
   3. for each parent finding its children
   4. remove the children from the list of nodes at that level
   5. putting the children into an array keyed on the parent
   6. repeat through the remaining nodes of that level
   7. marshaling the array
   8. going up a level

Others used to dealing with hierarchical tree structure using XML or similar
may have a "design pattern". Any suggestions? Alternatively might give up,
and see if I can use forward tree walking and a more suitable data structure
like XML or the new arrays. Is backward walking of tree structures ever
necessary - or can the same thing generally be achieved with forward
walking?



More information about the use-livecode mailing list