Source of 25.13.java

Structures and functions

  1: // @author Frank M. Carrano, Timothy M. Henry
  2: // @version 5.0

  4: public void iterativeInorderTraverse()
  5: {
  6:    StackInterface<BinaryNode<T>> nodeStack = new LinkedStack<>();
  7:    BinaryNode<T> currentNode = root;

  9:    while (!nodeStack.isEmpty() || (currentNode != null))
 10:    {
 11:       // Find leftmost node with no left child
 12:       while (currentNode != null)
 13:       {
 14:          nodeStack.push(currentNode);
 15:          currentNode = currentNode.getLeftChild();
 16:       } // end while

 18:       // Visit leftmost node, then traverse its right subtree
 19:       if (!nodeStack.isEmpty())
 20:       {
 21:          BinaryNode<T> nextNode = nodeStack.pop();
 22:          // Assertion: nextNode != null, since nodeStack was not empty
 23:          // before the pop
 24:          System.out.println(nextNode.getData());
 25:          currentNode = nextNode.getRightChild();
 26:       } // end if
 27:    } // end while
 28: } // end iterativeInorderTraverse