http://qs321.pair.com?node_id=153403


in reply to Introduction to Tree::DAG_Node

Excellent node! But a minor quibble: my memories from my intro data structures course are not the strongest, but they suggest that your definition of a post-order traversal is slightly flawed: the Left-Right order of the leaf nodes should be preserved (that is, net should still precede store, and research precede development).

Not a major issue, of course, for an org chart--but it could be unfortunate if that happened to an expression tree. :-) (thanks to maverick for the link, and for confirming that I'm not totally nuts.)


If God had meant us to fly, he would *never* have given us the railroads.
    --Michael Flanders

Replies are listed 'Best First'.
Re: Re: Introduction to Tree::DAG_Node
by gmax (Abbot) on Mar 22, 2002 at 07:36 UTC
    You are right, of course. Thanks for pointing it out.
    I absentmindedly copied the sequence from the result of an early script where the nodes were in that order. Using the same structure that we have in the company example, the post-order traversal is correct. Just change "callback" into "callbackback" and the printout will be:
        net empl:  6  budget:    25000
    str empl:  8  budget:    65000
  sales empl: 14  budget:    90000
  pers  empl:  4  budget:    10000
    res empl: 10  budget:   100000
    dev empl: 15  budget:    90000
  R&D   empl: 25  budget:   190000
company empl: 43  budget:   290000
              |
          <company>
     /--------+---------\
     |        |         |
  <sales>   <pers>    <R&D>
  /-----\            /-----\
  |     |            |     |
<net> <str>        <res> <dev>

    [download]
     _  _ _  _  
(_|| | |(_|><
 _|
[reply]
[d/l]

In Section Tutorials