The Tree Container Library

In the TCL, iterators are used to traverse the breadth and depth of the tree containers. There are a couple different categories of iterators in the TCL. The main way to categorize the iterators is by the way they iterate over the nodes in the trees. In this respect, there are four types of iterators, listed below.

• Child Iterators
  Used to iterate over the immediate children of a node.
• Reverse Child Iterators
  Used to iterate over the immediate children of a node in reverse order.
• Descendant Iterators
  Used to iterate over the descendants of a tree or subtree. The descendant iterators traverse the breadth and depth of a tree/subtree. There are three popular methods for traversing a tree structure, and three types of descendant iterators to provide these traversals:
  • Pre Order
    In this traversal, the parent node is visited first, followed immediately by any children of that node, from left to right.
  • Post Order
    In this traversal, all children are visited first from left to right, then the children's parent.
  • Level Order
    In this traversal, each level of the tree structure is visited in order, from top to bottom.
• Ordered Iterators
  These iterators are available only for unique_tree. They offer an alternate ordering scheme for the child nodes within their parent.

The TCL iterators can also be categorized by what they expose. To understand this concept, a good understanding is needed to differentiate between a node and an element. In the TCL, a node is considered to part of the tree structure itself. A node is used to contain the data, or elements, in the tree container. Each node in a tree structure has the same property of the tree itself. In fact, any operation which can be performed on the tree structure can also be performed (with a few exceptions) on any node in the tree structure. The nodes are in fact, subtrees within the structure.

Elements, on the other hand, are the data which is stored in the tree container. Each node in the tree structure contains an element. You decide what the elements will be in your own tree structures. The elements can be a basic type, such as and int or double, or can be a user defined type.

Now, the child, reverse, and descendant iterators all come in two varieties, which depends on what the iterators expose. Both iterator types iterate in the same fashion. The only difference is what is returned by the iterators dereference operator and pointer operator.

• Element Iterators
  Element iterators return a pointer/reference to the underlying element, with the -> and * operators, repectively.
• Node Iterators
  Node iterators return a pointer/reference to the underlying node, with the -> and * operators, respectively.

Normally, you will use the element iterators for most of your needs. The child element iterators are those that the TCL uses as return values from many of it's operations, like find(). These iterators are used so much more than the node iterators, that they are not given an element prefix, like the node iterators and operations are given.

And, of course, all the iterators come both the const and non-const varieties.