Does it make sense to implement iterators for containers which has no obvious end - e.g. trees?

Question

I`m writing binary search tree template for two reasons - learning C++ and learning most common algorithms and data structures.
So, here is the question - as long as I want to implement iterators, it seems to me that there is no strict definition for where tree ends. What are your suggestions? How do I do this?

Answer 1

For trees, there are standards for traversing the tree, i.e. enumerating the nodes: Preorder traversal, inorder traversal, and postorder traversal. Rather than describe all these here, I'll redirect you to http://en.wikipedia.org/wiki/Tree_traversal. The concepts are mostly applied to binary trees, but you can extend the idea to arbitrary trees by adding more cases: Effectively, handle a node then recurse, recurse then handle a node, handle all children then recurse into each...etc. There's no canonical categorization of this approach that I'm aware of.

Answer 2

If by 'strict' you mean: a single all encompassing definition, you're right, there isn't one.

But 'end' for trees is very well defined, although dependent on the traversal method you're choosing.

• If you do inorder (or symmetric) traversal, the rightmost element would be end.
• in preorder (or depth first), the rightmost element would be end, etc.
• in postorder, the root element would be end, etc.

Most common tree traversal methods.

Answer 3

It depends on what you want to do with the tree - maybe it would be nice to have, for instance, Breadth-First-Search or Depth-First-Search (or both) iterators.

If you have some particular way of scouring the tree, then in effect you do have a beginning and an end. It's not as obvious as the linear relations in lists and sets, but it's there if you want to impose some ordering on it.

Answer 4

You have to keep something clear when writing an iterator - an iterator for a data structure provides access to a collection as a linear sequence of items. Certain collections, like arrays, lists, and queues, are naturally compatible with being treated as a linear sequence. Other types of collections - trees, dictionaries, graphs - do not necessarily have a simple interpretation as a linear list. In fact, multiple interpretations are generally valid.

What you really to do when writing an iterator for a collection like a tree is address the following concerns:

1. Where does iteration of the collection begin (root? leaves?)
2. How does iteration progress to the next element (infix? postfix? suffix? breadth?)
3. When does iteration terminate (leaves? root? final node?)

Whatever you choose, you should be very clear in how you name (and document) your iterator to make it obvious how it will visit and emit nodes.

You may need to write multiple iterators for the different kinds of traverals you intend to support. There are some good articles here that dicuss tree traversal models.

Answer 5

Your definition of an iterator is slightly wrong. Iterators don't go from start to finish, nor front to back. Instead they go across all members of that structure.

If you ask for iteration over an ordered structure, ie an array, linked list etc, you'll (usually) get your members returned in-order.

For unordered items, eg a set, you'll get them in which ever order the set-iterator wants to give you them, but you'll get them all and one-at-a-time, just like you will with an array-iterator.

As for trees, other people have already mentioned: they have a well defined notions of total order, you just have to pick one :)