Source of 25.38.java

Structures and functions

  1: private NodePair getNodeToRemove(BinaryNode<T> currentNode)
  2: {
  3:    // Find node with largest entry in left subtree by
  4:    // moving as far right in the subtree as possible
  5:    BinaryNode<T> leftSubtreeRoot = currentNode.getLeftChild();
  6:    BinaryNode<T> rightChild = leftSubtreeRoot;
  7:    BinaryNode<T> priorNode = currentNode;
  8: 
  9:    while (rightChild.hasRightChild())
 10:    {
 11:       priorNode = rightChild;
 12:       rightChild = rightChild.getRightChild();
 13:    } // end while
 14: 
 15:    // rightChild contains the inorder predecessor and is the node to
 16:    // remove; priorNode is its parent
 17: 
 18:    return new NodePair(rightChild, priorNode);
 19: } // end getNodeToRemove
 20: // Version 4.0