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