迭代器

一分耕耘，一分收获！既然都打开这篇《迭代器》，就坚持看下去，学下去吧！本文主要会给大家讲到等等知识点，如果大家对本文有好的建议或者看到有不足之处，非常欢迎大家积极提出！在后续文章我会继续更新文章相关的内容，希望对大家都有所帮助！

BST 是可迭代的，因为它被定义为 java.lang.Iterable 接口的子类型。

方法inorder()、preorder()和postorder()以二叉树的形式显示inorder、preorder和postorder中的元素。这些方法仅限于显示树中的元素。如果您希望处理二叉树中的元素而不是显示它们，则不能使用这些方法。回想一下，提供了一个迭代器来遍历集合或列表中的元素。您可以在二叉树中应用相同的方法来提供遍历二叉树中元素的统一方式。

java.lang.Iterable接口定义了iterator方法，该方法返回java.util.Iterator接口的实例。 java.util.Iterator 接口（见下图）定义了迭代器的共同特性。

Tree 接口扩展了 java.lang.Iterable。由于BST是AbstractTree的子类，并且AbstractTree实现了Tree，所以BST是Iterable的子类型。 Iterable 接口包含 iterator() 方法，该方法返回 java.util.Iterator.

您可以按中序、前序或后序遍历二叉树。由于inorder的使用频率很高，所以我们将使用inorder来遍历二叉树中的元素。我们定义一个名为InorderIterator的迭代器类来实现BST.java中的java.util.Iterator接口（第219-263行）。 iterator 方法仅返回 InorderIterator 的实例（第 215 行）。

InorderIterator 构造函数调用 inorder 方法（第 225 行）。 inorder(root) 方法（第 234-239 行）将树中的所有元素存储在 list 中。元素按中序.

一旦创建了Iterator对象，它的current值就被初始化为0（第222行），它指向列表中的第一个元素。调用 next() 方法返回当前元素，并将 current 移动到指向列表中的下一个元素（第 250 行）。

hasNext()方法检查current是否仍在list的范围内（第243行）。

方法从树中删除当前元素（第 256 行）。然后，创建一个新列表（第 257-258 行）。请注意，current不需要更改。 下面的代码给出了一个测试程序，它将字符串存储在 BST 中并以大写形式显示所有字符串。

foreach 循环（第 15-16 行）使用迭代器来遍历树中的所有元素。

迭代器是一种重要的软件设计模式。它提供了一种遍历容器中元素的统一方法，同时隐藏容器的结构细节。通过实现相同的接口

，您可以编写一个以相同方式遍历所有容器的元素的程序。

定义了一个前向迭代器，它向前遍历迭代器中的元素，每个元素只能遍历一次。 Java API 还提供了java.util.ListIterator，支持向前和向后遍历。如果您的数据结构保证灵活遍历， 您可以将迭代器类定义为 java.util.ListIterator
. 的子类型 迭代器的实现效率不高。每次通过迭代器删除一个元素时，都会重建整个列表（BST.java 中的第 257 行）。客户端应始终使用

类中的 delete 方法来删​​除元素。为了防止用户在迭代器中使用remove方法，请按如下方式实现迭代器： 公共无效删除（）{

(“不支持从迭代器中删除元素”);
}

使迭代器类不支持

方法后，您可以更高效地实现迭代器，而无需维护树中元素的列表。您可以使用堆栈来存储节点，堆栈顶部的节点包含 next() 方法要返回的元素。如果树是平衡的，最大堆栈大小将为 O(logn)。

好了，本文到此结束，带大家了解了《迭代器》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！