The Tree Container Library
A C++ generic tree container library which, not only works much like the STL, but is also compatible with the STL algorithms. The Tree Container Library is used worldwide in thousands of industries and organizations. It is completely free to use, and is licensed under the zlib/libpng license.
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_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.
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.
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.
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
level_order_iterator. With a
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.
const_pre_order_iterator pre_order_begin() const
const_pre_order_iterator pre_order_end() const
const_post_order_iterator post_order_begin() const
const_post_order_iterator post_order_end() const
const_level_order_iterator level_order_begin() const
const_level_order_iterator level_order_end() const