使用C++ 11在二进制(或任意)树上实现迭代器

Question

我想在二叉树上创建一个迭代器,以便能够使用基于范围的for循环.我知道我应该首先实现begin()和end()函数.

开始应该指向根.但是,根据规范,end()函数返回"最后一个有效元素后面的元素".哪个元素(节点)是那个？指向某个"无效"的地方不是非法的吗？

另一件事是运算符++.在树中返回"next"元素的最佳方法是什么？我只需要一些建议就可以从这个编程开始.

---

我想扩大/扩充我的问题*.如果我想迭代一个任意arity的树怎么办？让每个节点都有一个子向量,让begin()指向"真正的"根.我可能不得不在迭代器类中实现一个队列(forstth-first)来将unique_ptr存储到节点,对吗？然后,当队列为空时,我知道我已经传递了所有节点,因此在调用oprator ++()时应该返回TreeIterator(nullptr).是否有意义？我希望它尽可能简单,只需要前向迭代.

*或者我应该创建一个新线程？

Answer 1

您begin()应该指向的地方几乎取决于您想要遍历树的顺序.使用根可能是明智的,例如,对于树的广度第一次行走.它end()实际上并不位于树节点上:访问此位置并指示已到达序列的末尾.它是否表示与树相关的任何内容在某种程度上取决于您想要支持的迭代类型:当仅支持前向迭代时,它只能指示结束.当还支持双向迭代时,它需要知道如何在结束之前找到节点.

在任何情况下,指向的地方都没有真正访问过,你需要一个合适的指标.对于正向迭代,只有迭代器end()可以返回指向null的迭代器,当你从最后一个节点继续时,你只需将迭代器的指针设置为null:比较两个指针的相等性将产生true,表明你已经到达终点.如果想要支持双向迭代,你需要某种可以用来导航到一个节点,但它并不需要存储的值路段记录的.

有序关联容器(std::map<K, V>,std:set<V>等)在内部实现为某种树(例如,红/黑树).该begin()迭代器最左边的节点开始和end()迭代器指的是最右边的节点后的位置.在operator++()刚刚找到下一个节点到当前的权利:

• 如果迭代坐在一个节点上没有右子节点,它沿着父母的链走,直到它找到一个父通过树的左支到达其子
• 如果它位于具有右子节点的节点上,则它会走向该子节点,然后向下移动该子节点的左子节点序列(如果有的话),以找到右子树中最左侧的子节点.

显然,如果你不是从左到右走树,而是从上到下走你的树,你需要一个不同的算法.对我来说最简单的方法是在一张纸上画一棵树,看看如何到达下一个节点.

如果您还没有使用自己的迭代器实现数据结构,我建议您尝试使用简单的顺序数据结构,例如列表:在那里,如何到达下一个节点以及何时到达终点是非常明显的.一旦通用迭代原理明确,创建树只是导航正确的问题.

Answer 2

看看RBTree的SGI实现(这是std::set/ std::map...容器的基础).

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

您将看到begin()是最左侧的节点.

你会看到end()是一个特殊的"空"节点头,它是超级根 - 我的意思是一个真正的根(仅当树不为空时预设)是它的子节点.

operator ++是去正确的孩子,然后找到这个孩子最左边的节点.如果这样的子节点不存在 - 我们转到最右边父节点的左侧父节点.如在这个例子中(红线是跳过移动,蓝色端是迭代的给定步骤):

从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()空树匹配此条件.

这似乎是非常智能的迭代方案.

当然,您可以定义自己的方案 - 但所学到的经验教训是有特殊节点用于end()目的.