christopher diggins wrote:
Why not have just one kind of iterator:
template<typename T, typename Iter_T> struct tree { typedef typename Iter_T iterator; iterator preorder_begin(); iterator postorder_end(); iterator inorder_end(); iterator end(); iterator begin(); // calls inorder_begin() }
?
Hm... That looks too much like a Sequence to me ;) I think this is not feasible in the general case. Consider a minimal node containing only a pointer to the next sibling and to the first child. Or a binary tree that keeps pointers to its left and right children. Inorder, preorder and postorder traversals are possible using a stack of ancestors. In the general case, though you shouldn't have to pay for this extra overhead at all times. IMO a tree container should be just that. Preorder, postorder and inorder are ways to turn a tree into a sequence, I see them as views of the tree. This is the main reason I'd prefer to have them as separate entities. Btw, here's my short view of a tree: template <typename T> struct Tree { typedef /**/ tree_iterator; typedef /**/ const_tree_iterator; typedef /**/ sibling_iterator; typedef /**/ const_sibling_iterator; tree_iterator root(); tree_const_iterator root() const; }; sibling_iterators are provided by the tree_iterator (they may be the same type). A set of tree_iterator_traits would describe their capabilities. Here's a taste of what I have in mind and partially in code... typedef tree<int> tree; typedef tree<int>::tree_iterator tree_iterator; typedef inorder_iterator<tree_iterator> inorder_iterator; tree t; ... insert data somehow ... tree_iterator it = t.root(); // traversal of level 1 for_each( it.children_begin(), it.children_end(), print_out("first generation")); it.descend(); assert(it); // implicit bool checks if we're a leaf // inorder traversal of subtree through iterators for_each( inorder_iterator(it), inorder_iterator(), print_out("subtree inorder")); // functional traversal inorder_traversal(it, print_out("subtree inorder (again)")); Best, João