使用C++11实现二叉树（或任意树）的迭代器

Question

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

Begin应该指向根节点。然而，根据规定，end()函数返回“最后一个有效元素之后的元素”。这个元素（节点）是什么？指向某个“无效”的位置不合法吗？

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

---

我想扩展/增强我的问题。如果我想遍历具有任意分支度的树怎么办？让每个节点都有一个子节点的向量，并让begin()指向“真正”的根。我可能要在迭代器类中实现一个队列（用于广度优先），以存储指向节点的unique_ptr，对吗？然后，当队列为空时，我会知道已经遍历完所有节点，因此在调用oprator++()时应返回TreeIterator(nullptr)。这有意义吗？我希望它尽可能简单，只进行前向迭代。

*还是应该创建一个新线程？

- Slazer

---

你的end()迭代器可能最终会成为一个在树中并非实际节点的特殊值。 - Lily Ballard

Answer 1

begin()方法指向的位置基本取决于您希望遍历树的顺序。使用根节点可能是明智的，例如用于广度优先遍历。而end()并不真正位于树节点上：该位置标志着遍历结束。它是否表示与树相关的内容在某种程度上取决于您想支持的迭代类型：仅支持正向迭代时，它可以表示结束; 当您还想支持双向迭代时，需要知道如何找到结束前的节点。

无论如何，所指向的位置并不真正被访问，您需要一个合适的指示器。对于仅支持正向迭代的迭代器，end()可以返回指向null的迭代器，并且当您从最后一个节点移动时，也将迭代器的指针设置为null：相等比较这两个指针将产生true，表示您已经到达了结尾。当希望支持双向迭代时，您需要一些链接记录，可用于导航到前一个节点，但不需要存储值。

有序关联容器（std::map<K，V>，std:set<V>等）内部实现为一种树（例如红黑树）。begin()迭代器从最左边的节点开始，而end()迭代器则指向右侧最后一个节点之后的位置。operator++()方法只是找到当前节点右侧的下一个节点：

• 如果迭代器位于一个没有右子节点的节点上，则沿着父节点链走直到找到一个通过树的左支到达其子节点的父节点。
• 如果它位于具有右子节点的节点上，则先走到该子节点，然后沿着此子节点的左子节点序列（如果有）向下寻找右子树中最左边的子节点。

显然，如果您不是从左到右遍历树，而是例如从上到下遍历，则需要使用不同的算法。对我来说最简单的方法是在纸上绘制一棵树，看如何到达下一个节点。

如果您还没有使用自己的迭代器实现数据结构，我建议您在简单的连续数据结构（例如列表）上尝试一些操作：在那里，如何到达下一个节点以及何时到达末尾都非常明显。一旦掌握了通用的迭代原则，创建树只是正确导航的问题。

- Dietmar Kühl

Answer 2

查看SGI实现的RBTree（这是std :: set / std :: map等容器的基础）。

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

你会发现begin()是最左边的节点。

你会发现end()是一个特殊的“空”节点header，它是超级根 - 我的意思是真正的根（仅在树不为空时预设）是其子节点。

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

- PiotrNycz

---

为什么始终要保持begin()==end()？在这个教程中，作者实现了一个数组迭代器，但这个条件并不成立。 - Slazer

我只是针对空树而言的这个条件 ;) - PiotrNycz

如果_M_node->_M_right != __y，那么_M_node将会等于__y。但是__y是_M_node的父节点，所以_M_node->_M_right怎么可能等于__y呢？这种情况怎么可能返回false呢？ - Fayeure

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)

你的 begin 迭代器指向什么取决于你想要的遍历类型。如果你正在进行广度优先遍历，则从根节点开始是有意义的。

- Vaughn Cato