Java Reference
In-Depth Information
The
Tree
interface extends
java.lang.Iterable
. Since
BST
is a subclass of
AbstractTree
and
AbstractTree
implements
Tree
,
BST
is a subtype of
Iterable
.
The
Iterable
interface contains the
iterator()
method that returns an instance of
java.util.Iterator
.
You can traverse a binary tree in inorder, preorder, or postorder. Since inorder is used
frequently, we will use inorder for traversing the elements in a binary tree. We define an
iterator class named
InorderIterator
to implement the
java.util.Iterator
inter-
face in Listing 25.5 (lines 221-263). The
iterator
method simply returns an instance of
InorderIterator
(line 217).
The
InorderIterator
constructor invokes the
inorder
method (line 228). The
inorder(root)
method (lines 237-242) stores all the elements from the tree in
list
. The
elements are traversed in
inorder
.
Once an
Iterator
object is created, its
current
value is initialized to
0
(line 225), which
points to the first element in the list. Invoking the
next()
method returns the current element
and moves
current
to point to the next element in the list (line 253).
The
hasNext()
method checks whether
current
is still in the range of
list
(line 246).
The
remove()
method removes the current element from the tree (line 259). Afterward, a
new list is created (lines 260-261). Note that
current
does not need to be changed.
Listing 25.11 gives a test program that stores the strings in a BST and displays all strings
in uppercase.
how to create an iterator
L
ISTING
25.11
TestBSTWithIterator.java
1
public class
TestBSTWithIterator {
2
public static void
main(String[] args) {
3 BST<String> tree =
new
BST<>();
4 tree.insert(
"George"
);
5 tree.insert(
"Michael"
);
6 tree.insert(
"Tom"
);
7 tree.insert(
"Adam"
);
8 tree.insert(
"Jones"
);
9 tree.insert(
"Peter"
);
10 tree.insert(
"Daniel"
);
11
12
for
(String s: tree)
13 System.out.print(s.toUpperCase() +
" "
);
14 }
15 }
use an iterator
get uppercase letters
ADAM DANIEL GEORGE JONES MICHAEL PETER TOM
The foreach loop (lines 12-13) uses an iterator to traverse all elements in the tree.
Design Guide
Iterator is an important software design pattern. It provides a uniform way of traversing
the elements in a container, while hiding the container's structural details. By imple-
menting the same interface
java.util.Iterator
, you can write a program that
traverses the elements of all containers in the same way.
iterator pattern
advantages of iterators
Note
java.util.Iterator
defines a forward iterator, which traverses the elements in
the iterator in a forward direction, and each element can be traversed only once. The
Java API also provides the
java.util.ListIterator
, which supports traversing in
both forward and backward directions. If your data structure warrants flexible traversing,
you may define iterator classes as a subtype of
java.util.ListIterator
.
variations of iterators
Search WWH ::
Custom Search