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

Question

我正在编写二进制搜索树模板有两个原因 - 学习C++并学习最常见的算法和数据结构.
所以,这里有一个问题 - 只要我想实现迭代器,在我看来,树的结束没有严格的定义.你有什么建议？我该怎么做呢？

Answer 1

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

Answer 2

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

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

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

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

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