Source of 26.38.java

Structures and functions

  1: // @author Frank M. Carrano, Timothy M. Henry
  2: // @version 5.0
  3: private NodePair getNodeToRemove(BinaryNode<T> currentNode)
  4: {
  5:    // Find node with largest entry in left subtree by
  6:    // moving as far right in the subtree as possible
  7:    BinaryNode<T> leftSubtreeRoot = currentNode.getLeftChild();
  8:    BinaryNode<T> rightChild = leftSubtreeRoot;
  9:    BinaryNode<T> priorNode = currentNode;

 11:    while (rightChild.hasRightChild())
 12:    {
 13:       priorNode = rightChild;
 14:       rightChild = rightChild.getRightChild();
 15:    } // end while

 17:    // rightChild contains the inorder predecessor and is the node to
 18:    // remove; priorNode is its parent

 20:    return new NodePair(rightChild, priorNode);
 21: } // end getNodeToRemove