Walking Trees Backwards

[Randall Reetz]

If you aren't a computer scientist then what kind of scientist are you?  If you have code that builds trees as indented outlines then walking down them usually just means moving back up the text file line by line untill there are one less tabs in front of a line, etc.  If you bracket your leading tabs with a special char then you can search for the correct number of tabs if you can use find or offset in reverse... Or on a flipped instance of the text.  If you are constantly navigating and never pruning or adding to your trees it is sometimes more efficient to store complete ancestor pathes with each leaf or branc.  If you learn to always keep the current complete path as you swim around your tree you can navigate far easer (or in this specific case you wouldnt have to... Just move backwards down your path).  Does any of this help?  

-----Original Message-----
From: "David Bovill" <david at architex.tv>
To: "How to use Revolution" <use-revolution at lists.runrev.com>
Sent: 9/11/2008 7:43 AM
Subject: Walking Trees Backwards

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?
_______________________________________________
use-revolution mailing list
use-revolution at lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-revolution