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

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 3

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 4

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 :)

Answer 5

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 6

It makes sense especially in cases like that, because gives users of your class a way to easily walk over all elements in different ways as the situation requires. Without them, users need to write complicated, usually recursive ways themselves. Compared to e.g. vectors where iterators are more typing than using for(i=0;i

Answer 7

I think in iterator in a more abstract way. I don't see in the iterator pattern nothing that really says there's a beginning or an end! So, why the be constrained to that vision. We can imagine iterator that only concerns about the next element, that's all. I mean, I have faced (specially in mass processing) situations where since the beginning we don't know the extension of the collection, we don't know if it will have an end some day , or we don't have all their elements loaded in memory, and we don't care. We only care about getting the next element. In one of those implementations the next node is created just after the next element method is call. We can open our minds and think on infinite collections (at the end a collection is a type of mathematical set) like the collections of all the numbers, the collection of all the random numbers. You don't have to actually have all the elements in memory (that's obvious for infinite collections). Of course this are not practical examples, but my message is that a user of an Iterator doesn't have to rely of the actual structure or extension of a collection. JUST GIVE ME THE NEXT (IF YOU HAVE IT).