Iterate over nodes in a tree

Question

I want to make an iterator that can handle my selfmade structs:

struct node {
int n; //data element
node * parent;
node * left;
node * right;  
node (int elem): n(elem){ //create root
     parent = NULL; left = NULL; right = NULL;
}
node (int elem, node* p): n(elem), parent(p) { //addchild
    left = NULL;
    right = NULL; 
}
node(int elem, node * p, node * l, node * r): n(elem), parent(p), left(l), right(r){ //insert element
}
};

First of all, is this possible? If yes: how do I start to make the iterator that traverses the tree. If not: what do you suggest for me to do if I want to access data elements in the list.

Answer 1

Yes.

Hint: Your iterator, when it advances, should go to the parent and figure out whether it's a left child or right child of that parent. That will tell you where to go next.

Answer 2

Yes, given the node structure you've outlined with a right pointer (which presumably points to the next node in traversal order), implementing a forward iterator should be quie easy.

The basic idea is something like this:

template <class Node>
class iterator { 
    Node *pos;
public:
    iterator(Node *tree = nullptr) : pos(tree) {}
    iterator operator++() { pos = pos->right; return *this; }
    Node &operator*() { return *pos; }
    bool operator!=(iterator const &other) const { return pos != other.pos; }
};

There is a little more than that involved in a real iterator though. In particular, you normally (always?) want to specify things like the value_type, reference_type and category of the iterator. Most of these are pretty close to pure boilerplate though, and you can handle most of them by deriving from std::iterator.

You also (typically) want to support a few more operations than I've shown here, such as post-fix increment, operator==, etc. Given this as a "framework", I think filling in those blanks should be fairly straightforward though.

I should probably also point out the existence of the Boost iterators library. This simplifies the task of implementing an iterator (somewhat) and cuts down on the boilerplate you have to write (quite a bit).