1回答

liuyubobobo

2018-08-20

已采纳

首先，你必须已经熟练的使用了迭代器，了解迭代器的所有方法，怎么创建，怎么使用。建议你首先整理一下java的标准库中各个不同的容器类的迭代器的使用方法（其实是相同的），整理成一个你头脑中的概念，从一个更加高层的视角审视迭代器到底是什么。创建一个类的底层实现的第一步，是要知道这个类到底要干什么。这个干什么不能泛泛而谈，而应该落成到每一个方法接口，他的输入是什么，输出是什么，用户应该在什么情况下如何调用。

如果你已经有了这个基础概念，可能再去看很多网上的文章，就会舒服很多。Leetcode上173号问题就是创建一个二分搜索树的迭代器，可以参考。

传送门：

英文版：https://leetcode.com/problems/binary-search-tree-iterator/description/

中文版：https://leetcode-cn.com/problems/binary-search-tree-iterator/description/

注意：173号问题是设计的是一个单独的迭代器类，所以整个二分搜索树是以参数的形式（根节点）传入这个迭代器类的构造函数的。如果在你自己的容器类中设计迭代器类，迭代器类可以作为这个容器类的内部类，所以可以直接访问到容器类中的所有内容：）

对于173号问题我的参考代码（C++）：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0173-Binary-Search-Tree-Iterator/cpp-0173/main3.cpp

在这里，还有一个关键，就是，做二分搜索树的迭代器，你必须熟悉二分搜索树的前序遍历的非递归实现。这是逻辑层面，而非类设计层面。如果理解了迭代器到底是怎么回事儿，而不很理解二分搜索树的前序遍历非递归实现，依然实现不了。此时可以首先，尝试自己实现线性数据结构（如动态数组和链表）的迭代器，对迭代器有更深入的认识以后，进一步研究二分搜索树的前序非递归遍历逻辑，最后完成二分搜索树的迭代器。

我的《算法与数据结构》课程中，在实现图结构时，对于图中某一个节点的相邻节点的遍历，使用了自己设计的迭代器，其实本质就是线性数据结构的迭代器（因为每一个节点存储其相邻节点，使用的是线性结构），如果认为有必要，也可以参考：

C++代码：

稠密图：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/07-Graph-Basics/Course%20Code%20(C%2B%2B)/03-Vertex%20Adjacent%20Iterator/DenseGraph.h

稀疏图：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/07-Graph-Basics/Course%20Code%20(C%2B%2B)/03-Vertex%20Adjacent%20Iterator/SparseGraph.h

Java代码：

稠密图：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/07-Graph-Basics/Course%20Code%20(Java)/03-Vertex-Adjacent-Iterator/src/bobo/algo/DenseGraph.java

稀疏图：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/07-Graph-Basics/Course%20Code%20(Java)/03-Vertex-Adjacent-Iterator/src/bobo/algo/SparseGraph.java

最后，个人建议，如果现在你还没有学习完整个课程的话，先学习整个课程。迭代器的设计和实现已经一定程度超出了一般的算法和数据结构的范畴了，而更多的在类设计，标准库设计，设计模式的相关范畴。先把这个课程的内容掌握，再向外发散。抓大放小，先解决主要矛盾。不要因为一个根本不在课程范围内的迭代器，而没有学习课程后续所讲的数据结构领域非常重要的内容，如堆；平衡二叉树；哈希表等。

加油！：）

2

1

the__sky123

非常感谢老师的耐心解答！

2018-08-20

共1条回复