Walking Trees Backwards

[David Bovill]

2008/9/11 Randall Reetz <randall at randallreetz.com>

> 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?


Thanks Randal. Science was a while ago - lets just say I wasn't a dentist.
Everything you say above gels with how the library works for outlines - so
its good to know its the right sort of approach. But it does not help with
backward walking from leaves to trunk - largely because of issues like where
do you start? Which leaf? Does the order matter? Thinking again this is not
going to be recursive, you just need to repeat through each leaf. Maybe its
not so hard....


-----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
>
>
> _______________________________________________
> 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
>