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