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行）。

remove() 方法从树中删除当前元素（第 256 行）。然后，创建一个新列表（第 257-258 行）。请注意，current不需要更改。

下面的代码给出了一个测试程序，它将字符串存储在 BST 中并以大写形式显示所有字符串。

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

迭代器是一种重要的软件设计模式。它提供了一种遍历容器中元素的统一方法，同时隐藏容器的结构细节。通过实现相同的接口java.util.Iterator，您可以编写一个以相同方式遍历所有容器的元素的程序。

java.util.Iterator定义了一个前向迭代器，它向前遍历迭代器中的元素，每个元素只能遍历一次。 Java API 还提供了java.util.ListIterator，支持向前和向后遍历。如果您的数据结构保证灵活遍历，
您可以将迭代器类定义为 java.util.ListIterator. 的子类型

迭代器的实现效率不高。每次通过迭代器删除一个元素时，都会重建整个列表（BST.java 中的第 257 行）。客户端应始终使用 BinraryTree 类中的 delete 方法来删??除元素。为了防止用户在迭代器中使用remove方法，请按如下方式实现迭代器：

公共无效删除（）{
抛出新的 UnsupportedOperationException
(“不支持从迭代器中删除元素”);
}使迭代器类不支持remove方法后，您可以更高效地实现迭代器，而无需维护树中元素的列表。您可以使用堆栈来存储节点，堆栈顶部的节点包含 next() 方法要返回的元素。如果树是平衡的，最大堆栈大小将为 O(logn)。

    以上就是迭代器的详细内容，更多请关注php中文网其它相关文章！