It is no-where as cool as implicit python iterators, but it may be useful every now and then.
It is usually used like this:
Iterator e = container.iterator(); while (e.hasNext()) { System.out.println(e.next()); }How do we implement a binary search tree iterator?
Look at the code here for binary search tree iterative traversal.
A simplest solution would be to "print" a tree into a storage array and then allow the iterator to operate on this array.
Alternatively (as shown here), we can use the iterative method developed earlier to maintain iterator state.
A basic idea for this iterator is saving a pointer (I call it a cursor) to a most recently found element.
Since the iterator has to access a lot of the tree's internals, I like to declare it as a private class inside my binary search tree implementation.
Such an approach ensures that variables such as tree.root are not seen from the outside.
Here is a simple implementation of an iterator that allows in-order traversal:
private class BSTIterator implements Iterator { Node root, cursor; StackThe things to notice here are that we just broke up the iterative method into separate chunks inside this class.iteratorStack; public BSTIterator (BSTNode root) { this.root = root; this.cursor = root; this.iteratorStack = new Stack (); } public boolean hasNext() { return (!iteratorStack.empty() || cursor != null); } public Comparable next() { Comparable nextNodeValue; while (cursor != null) { iteratorStack.push(cursor); cursor = cursor.leftChild; } cursor = iteratorStack.pop(); nextNodeValue = cursor.key; cursor = cursor.rightChild; return nextNodeValue; } }
All of our local variables moved to class globals.
The while condition became the hasNext() boolean.
The body of the iterative method was modified for next().
As a result, we get nice, clean, multipurpose code.
Hey man, Java does not allow private class to be declared.
ReplyDelete