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

Question

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

Begin可能会指向根目录。但是，根据规范，end()函数返回“最后一个有效元素之后的元素”。那是哪个元素(节点)？指出某个“无效”的地方不违法吗？

另一件事是operator++。在树中返回“下一步”元素的最佳方法是什么？我只是需要一些建议，从这个程序开始。

我想扩充我的问题*。如果我想以任意的方式迭代一棵树呢？让每个节点都有一个子节点向量，让begin()指向“真实”根。我可能需要在迭代器类中实现一个队列(对于宽度优先)来存储唯一的ptr到节点，对吗？然后，当队列为空时，我将知道我已经传递了所有节点，因此在调用oprator++()时应该返回oprator++(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的基础.)。

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()目的，要有特殊的节点。

Answer 3

树的迭代器将不仅仅是一个指针，尽管它可能包含一个指针：

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) { ... }

可以使end()函数返回一些特殊的内容，如TreeIterator(nullptr)

您的开始迭代器指向什么将取决于您想要的遍历类型。如果你是做宽度第一次遍历，然后从根开始是有意义的。