Re: [boost] any interest in a 'tree' container?

From: Terje Slettebø (tslettebo_at_[hidden])
Date: 2002-10-10 15:14:11

>From: "Samuel Krempp" <krempp_at_[hidden]>

>2 years ago I needed a tree class with iterators (depth-first AND
>breadth-first),

>I looked at your increment_() (I would call it iterate_, but well) and I
>think purists have a precise name for this iteration scheme. I was told
>my iteration was not true "depth-first", because it picks father before
>son, and I think your iteration is the same. I vaguely recall names like
>"prefix depth-first", or suffix, or whatever.. but you'd need to know
>the precise litterature name for this  for a boost submission.

           R
          /  \
         /    \
     L1     R1
     /  \
    /    \
L2     R2

I thought common names for this was (at least it's used in books on
algorithms and data structures):

Pre-order (children before parent): L2-R2-L1-R1-R
Post-order (children after parent): R-L1-L2-R2-R1
In-order: L2-L1-R2-R-R1
Level-order: L2-R2-L1-R1-R (or starting from the root)

How does this relate to depth-first, breadth-first, etc.?

Regards,

Terje