Source of 24.13.java

Structures and functions

  1: public void iterativeInorderTraverse()
  2: {
  3:    StackInterface<BinaryNode<T>> nodeStack = new LinkedStack<>();
  4:    BinaryNode<T> currentNode = root;
  5: 
  6:    while (!nodeStack.isEmpty() || (currentNode != null))
  7:    {
  8:       // Find leftmost node with no left child
  9:       while (currentNode != null)
 10:       {
 11:          nodeStack.push(currentNode);
 12:          currentNode = currentNode.getLeftChild();
 13:       } // end while
 14: 
 15:       // Visit leftmost node, then traverse its right subtree
 16:       if (!nodeStack.isEmpty())
 17:       {
 18:          BinaryNode<T> nextNode = nodeStack.pop();
 19:          assert nextNode != null; // Since nodeStack was not empty
 20:                                   // before the pop
 21:          System.out.println(nextNode.getData());
 22:          currentNode = nextNode.getRightChild();
 23:       } // end if
 24:    } // end while
 25: } // end iterativeInorderTraverse
 26: // Version 4.0