The Tree Container Library

Descendant element iterators iterate over a node's descendants. There are three types of descendant element iterators for the tree container library, the pre_order_iterator, post_order_iterator, and level_order_iterator. The pre_order_iterators and post_order_iterators are bi-directional iterators, while the level_order_iterators are forward-only iterators. The three types of descendant element iterators are described below. Illustrations to the right show how the three types of descendant iterators traverse a tree.

• pre_order_iterator and const_pre_order_iterator
  The pre_order_iterators traverse over nodes in a pre-order fashion. These iterators recurring visit a parent node first, then the nodes children, before going on the parent's sibling node.
• post_order_iterator and const_post_order_iterator
  The post_order iterators traverse over nodes in a post-order fashion. These iterators recurring visit a parent's children first, then visit the parent, before going on to the parent's sibling.
• level_order_iterator and const_level_order_iterator
  The level_order_iterators traverse over nodes in a level_order fashion. These iterators traverse child nodes, level by level. The first level would be considered the immediate children of a parent node. the second level would be considered the parent's grandchildren. The third level would be considered the parent's great grandchildren, and so on.

The descendant element iterators have the same interface and operations as the child element iterators. So you can perform all the same operations as on the child iterator. Unlike the inserting and erasing operations in the STL, performing an insert, or clear operation on an iterator's underlying node does not invalidate that iterator. This is because by performing one of these operations on an iterator's underlying node affects the node's children only. This does not mean that performing on of these operations will not have an effect on the transversal. Inserting or removing nodes via an iterator will most likely alter future iterations, especially if the iterator is a pre_order_iterator or level_order_iterator. With a post_order_iterator, the children have already been traversed before visiting the parent, so performing an insert or clear on the iterator will not effect the future iterations.

The only operations in the tree containers which return descendant element iterators are those operations which return the beginning and end of the iterators, as shown below.

• pre_order_iterator pre_order_begin()
pre_order_iterator pre_order_end()
const_pre_order_iterator pre_order_begin() const
const_pre_order_iterator pre_order_end() const
• post_order_iterator post_order_begin()
post_order_iterator post_order_end()
const_post_order_iterator post_order_begin() const
const_post_order_iterator post_order_end() const
• level_order_iterator level_order_begin()
level_order_iterator level_order_end()
const_level_order_iterator level_order_begin() const
const_level_order_iterator level_order_end() const