Alex Rivera | Logout

Implementing an iterator over binary (or arbitrary) tree using C++ 11

Asked 2012-10-02T03:35:58.760
11

I would like to create an iterator over the binary tree so as to be able to use range-based for loop. I understand I ought to implement the begin() and end() function first.

Begin should probably point to the root. According to the specification, however, the end() functions returns "the element following the last valid element". Which element (node) is that? Would it not be illegal to point to some "invalid" place?

The other thing is the operator++. What is the best way to return "next" element in tree? I just need some advice to begin with this programming.

I would like to expand/augment my question*. What if I wanted to iterate over a tree with an arbitrary arity? Let each node have a vector of children and let begin() point to the "real" root. I would probably have to implement a queue (for breadth-first) inside the iterator class to store the unique_ptr's to nodes, right? Then, when the queue is empty I would know that I have passed all nodes and thus should return TreeIterator(nullptr) when oprator++() is called. Does it make sense? I want it as simple as possible and only forward iteration.

*Or should I create a new thread?

c++ tree iterator
Edit
Report

1 Answer

11

Look at SGI implementation of RBTree (this is the base for std::set/std::map... containers).

http://www.sgi.com/tech/stl/stl_tree.h

You will see that begin() is the leftmost node.

You will see that end() is a special "empty" node header which is the super root - I mean a real root (preset only if the tree is not empty) is its child node.

operator ++ is to go to right child and then find this child leftmost node. If such child does not exist - we go to left parent of the rightmost parent node. As in this example (red lines are skip move, blue ones ends are the given steps of iteration):

enter image description here

The code copied from SGI:

  void _M_increment()
  {
    if (_M_node->_M_right != 0) {
      _M_node = _M_node->_M_right;
      while (_M_node->_M_left != 0)
        _M_node = _M_node->_M_left;
    }
    else {
      _Base_ptr __y = _M_node->_M_parent;
      while (_M_node == __y->_M_right) {
        _M_node = __y;
        __y = __y->_M_parent;
      }
      if (_M_node->_M_right != __y)
        _M_node = __y;
    }
  }

When a tree is empty - begin() is leftmost of header - so it is header itself - end() is also header - so begin() == end(). Remember - your iteration scheme must match this condition begin() == end() for empty trees.

This seems to be very smart iteration scheme.

Of course you can define you own scheme - but the lesson learned is to have special node for end() purpose.

answered 2012-10-02T04:53:23.547

Your Answer