Boost logo

Boost :

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

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

          / \
         / \
     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.?


