10

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

开始应该可能指向根。然而，根据规范，end() 函数返回“最后一个有效元素之后的元素”。那是哪个元素（节点）？指向一些“无效”的地方不是违法的吗？

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

我想扩展/增加我的问题*。如果我想遍历具有任意数量的树怎么办？让每个节点都有一个子节点向量，并让 begin() 指向“真正的”根。我可能必须在迭代器类中实现一个队列（对于广度优先）来将 unique_ptr 存储到节点，对吧？然后，当队列为空时，我会知道我已经通过了所有节点，因此应该在调用 oprator++() 时返回 TreeIterator(nullptr)。是否有意义？我希望它尽可能简单并且只向前迭代。

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

4

3 回答 3

13

您begin()应该指向的位置几乎取决于您要遍历树的顺序。使用根可能是明智的，例如，对于树的广度优先遍历。end()并不真正位于树节点上：访问此位置并指示已到达序列的末尾。它是否指示与树相关的任何内容在某种程度上取决于您要支持哪种迭代：当仅支持前向迭代时，它只能指示结束。当还支持双向迭代时，它需要知道如何在结束之前找到节点。

无论如何，所指向的地方并没有真正被访问，您需要一个合适的指标。对于前向迭代，只有迭代器end()可以只返回一个指向 null 的迭代器，当您从最后一个节点继续前进时，您只需将迭代器的指针也设置为 null：比较两个指针的相等性会产生true，表明您已经到达终点。当想要支持双向迭代时，您需要某种链接记录，可用于导航到前一个节点但不需要存储值。

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

  • 如果迭代器位于没有右子节点的节点上，它将沿着父节点链遍历，直到找到父节点通过树的左分支到达其子节点
  • 如果它位于具有右子节点的节点上，它会走到该子节点，然后沿着该子节点的左子节点序列（如果有的话）找到右子树中最左边的子节点。

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

如果您没有使用自己的迭代器实现数据结构，我建议您尝试使用简单的顺序数据结构，例如列表：如何到达下一个节点以及何时到达终点非常明显。一旦明确了一般的迭代原则，创建树只是获得正确导航的问题。

于 2012-10-02T03:50:38.850 回答
11

查看 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()是 header 的最左边 - 所以它是 header 本身 -end()也是 header - 所以begin() == end()。请记住 - 您的迭代方案必须与begin() == end()空树的条件相匹配。

这似乎是一个非常聪明的迭代方案。

当然，您可以定义自己的方案 - 但吸取的教训是要有专门的节点end()。

于 2012-10-02T04:53:23.547 回答
0

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

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)

您的开始迭代器指向的内容取决于您想要的遍历类型。如果您正在进行广度优先遍历，那么从根开始是有意义的。

于 2012-10-02T03:45:08.970 回答