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