c++ - 为没有明显结束的容器（例如树）实现迭代器是否有意义？

Question

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

Answer 1

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

Answer 2

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

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

1. 集合的迭代从哪里开始（根？叶子？）
2. 迭代如何进行到下一个元素（中缀？后缀？后缀？宽度？）
3. 迭代何时终止（离开？根？最终节点？）

无论您选择什么，您都应该非常清楚如何命名（和记录）您的迭代器，以使其访问和发出节点的方式一目了然。

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

Answer 3

如果您所说的“严格”是指：一个包罗万象的定义，那么您是对的，没有一个。

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

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

最常见的树遍历方法。

Answer 4

您对迭代器的定义略有错误。迭代器不是从头到尾，也不是从前到后。相反，它们会遍历该结构的所有成员。

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

对于无序的项目，例如一个集合，你会得到它们集合迭代器想要给你的任何顺序，但你会得到它们，一次一个，就像你用数组一样-迭代器。

至于树，其他人已经提到过：他们有一个明确定义的全序概念，你只需要选择一个:)

Answer 5

这取决于您想对树做什么 - 例如，拥有广度优先搜索或深度优先搜索（或两者）迭代器可能会很好。

如果你有某种特定的方法来擦树，那么实际上你确实有一个开始和一个结束。它不像列表和集合中的线性关系那么明显，但如果你想对其施加一些排序，它就在那里。

Answer 6

这在这种情况下尤其有意义，因为为您的类的用户提供了一种根据情况需要以不同方式轻松遍历所有元素的方法。没有它们，用户需要自己编写复杂的、通常是递归的方式。与迭代器比使用 for(i=0;i) 更多类型的向量相比

Answer 7

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