为没有明显终点的容器实现迭代器是否有意义 - 例如树？

Question

我编写二叉搜索树模板有两个原因 - 学习 C++ 和学习最常见的算法和数据结构。
所以，问题来了——只要我想实现迭代器，在我看来，树的结束位置并没有严格的定义。您有什么建议？我该怎么做呢？

Answer 1

对于树，有遍历树的标准，即枚举节点：Preorder遍历，inorder遍历和后序遍历。我将重定向到 http://en.wikipedia.org/wiki/Tree_traversal 。这些概念主要应用于二叉树，但您可以通过添加更多案例将想法扩展到任意树：有效地，处理节点然后递归，递归然后处理节点，处理所有子节点然后递归到每个...等。我不知道这种方法的规范分类。

Answer 2

编写迭代器时必须保持清晰 - 数据结构的迭代器提供对作为线性项目序列的集合的访问。某些集合（如数组，列表和队列）自然与被视为线性序列兼容。其他类型的集合 - 树，字典，图形 - 不一定具有作为线性列表的简单解释。事实上，多种解释通常是有效的。

在为像树一样的集合编写迭代器时，您真正要做的是解决以下问题：

1. 集合的迭代在哪里开始（root？leaves？）
2. 迭代如何进展到下一个元素（中缀？后缀？后缀？广度？）
3. 何时迭代终止（离开？root？final node？）

无论你选择什么，你应该非常清楚你如何命名（和记录）你的迭代器，以明确它将如何访问和发出节点。

您可能需要为要支持的不同类型的traveral编写多个迭代器。这里有一些很好的文章来讨论树遍历模型。

Answer 3

如果“严格”是指：一个单一的包罗万象的定义，你是对的，没有一个。

但是树的“结束”是非常明确的，尽管取决于您选择的遍历方法。

• 如果进行中序（或对称）遍历，最右边的元素将是 end.
• 在前序（或深度优先）中，最右边的元素是 end, ， ETC。
• 在后序中，根元素将是 end, ， ETC。

最常见的 树遍历 方法。

Answer 4

您对迭代器的定义有点错误。迭代器不会从开始到完成，也不会从开始到返回。相反，他们跨该结构的所有成员。

如果您要求对有序结构进行迭代，即数组，链表等，您（通常）会按顺序返回您的成员。

对于无序项目，例如一个集合，你会得到它们，其中曾经订购过set-iterator想要给你它们，但是你会一次一个地得到它们，就像你一样使用数组迭代器。

至于树木，其他人已经提到：他们有一个明确定义的总秩序概念，你只需选择一个：）

Answer 5

这取决于你想对树做什么 - 也许最好有，例如，广度优先搜索或深度优先搜索（或两者）迭代器。

如果你有一些特殊的方法来淘树，那么实际上你有一个开始和结束。它不像列表和集合中的线性关系那么明显，但是如果你想在它上面强加一些排序就可以了。

Answer 6

在这样的情况下，特别是是有道理的，因为为您的班级用户提供了一种在不同情况下以不同方式轻松遍历所有元素的方法。没有它们，用户需要自己编写复杂的，通常是递归的方式。与例如相比迭代器比使用for更多的类型的向量（i = 0; i     

Answer 7

我认为在迭代器中以更抽象的方式。我没有在迭代器模式中看到任何真正说明有开始或结束的东西！那么，为什么要限制这种愿景。我们可以想象迭代器只关注下一个元素，就是这样。我的意思是，我面临（特别是在大规模处理）的情况，从一开始我们不知道集合的扩展，我们不知道它是否会在某一天结束，或者我们没有他们所有的元素加载在内存中，我们并不在意。我们只关心获得下一个元素。在其中一个实现中，下一个节点是在调用下一个元素方法之后创建的。我们可以打开思想，思考无限集合（最后集合是一种数学集合），如所有数字的集合，所有随机数的集合。您不必实际拥有内存中的所有元素（这对于无限集合来说是显而易见的）。当然这不是实际的例子，但我的信息是Iterator的用户不必依赖于集合的实际结构或扩展。只是给我下一个（如果你有的话）。