private class InorderIterator implements Iterator
1: // @author Frank M. Carrano, Timothy M. Henry
2: // @version 5.0
4: private class InorderIterator implements Iterator<T>
5: {
6: private StackInterface<BinaryNode<T>> nodeStack;
7: private BinaryNode<T> currentNode;
9: public InorderIterator()
10: {
11: nodeStack = new LinkedStack<>();
12: currentNode = root;
13: } // end default constructor
15: public boolean hasNext()
16: {
17: return !nodeStack.isEmpty() || (currentNode != null);
18: } // end hasNext
20: public T next()
21: {
22: BinaryNode<T> nextNode = null;
24: // Find leftmost node with no left child
25: while (currentNode != null)
26: {
27: nodeStack.push(currentNode);
28: currentNode = currentNode.getLeftChild();
29: } // end while
31: // Get leftmost node, then move to its right subtree
32: if (!nodeStack.isEmpty())
33: {
34: nextNode = nodeStack.pop();
35: // Assertion: nextNode != null, since nodeStack was not empty
36: // before the pop
37: currentNode = nextNode.getRightChild();
38: }
39: else
40: throw new NoSuchElementException();
42: return nextNode.getData();
43: } // end next
45: public void remove()
46: {
47: throw new UnsupportedOperationException();
48: } // end remove
49: } // end InorderIterator