Geek asks and answers

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

I would like to create an iterator over a binary tree in order to be able to use a range based loop. I understand that I must first implement the begin () and end () functions.

Start should probably point to the root. However, according to the specification, end () functions return "the element following the last valid element". What element (node)? Wouldn't it be illegal to point to some “invalid” place?

Another thing is the ++ operator. What is the best way to return the "next" element in a tree? I just need some advice to get started with this programming.

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

* Or do I need to create a new thread?

+5
source share
3 answers

begin() , , . , , . end() node: , . , -, , , : . , , node .

, , , . end() , , node, : , , true, . , - , node, .

(std::map<K, V>, std:set<V> ..) (, Red/Black-tree). begin() node, end() node. operator++() node :

  • node node, , ,
  • node node, , ( ), .

, , , , , . - , node.

, , , , : , node . , - .

+9

SGI RBTree ( std::set/std::map...).

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

, begin() node.

, end() "" node , -root - ( , ) child node.

operator ++ - , node. , node. ( , - ):

enter image description here

, 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;
    }
  }

- begin() - - - end() - begin() == end(). - begin() == end() .

.

, - node end() .

+5

An iterator for a tree will be more than just a pointer, although it will most likely contain a pointer:

struct TreeIterator {
  TreeIterator(TreeNode *node_ptr) : node_ptr(node_ptr) { }
  TreeIterator &operator++();
  TreeIterator operator++(int);
  bool operator==(const TreeIterator &) const;

  private:
    TreeNode *node_ptr;
};

TreeIterator begin(const Tree &tree) { ... }
TreeIterator end(const Tree &tree) { ... }

You can force the end () function to return something special, for example TreeIterator(nullptr)

What your iterator points to will depend on the type of traversal you want. If you are doing a width traversal, then starting from the root makes sense.

0
source

More articles:


All Articles