Source of 26.32.java


  1: // Removes the entry in a given root node of a subtree.
  2: // rootNode is the root node of the subtree.
  3: // Returns the root node of the revised subtree.
  4: // @author Frank M. Carrano, Timothy M. Henry
  5: // @version 5.0
  6: private BinaryNode<T> removeFromRoot(BinaryNode<T> rootNode)
  7: {
  8:    // Case 1: rootNode has two children
  9:    if (rootNode.hasLeftChild() && rootNode.hasRightChild())
 10:    {
 11:       // Find node with largest entry in left subtree
 12:       BinaryNode<T> leftSubtreeRoot = rootNode.getLeftChild();
 13:       BinaryNode<T> largestNode = findLargest(leftSubtreeRoot);

 15:       // Replace entry in root
 16:       rootNode.setData(largestNode.getData());

 18:       // Remove node with largest entry in left subtree
 19:       rootNode.setLeftChild(removeLargest(leftSubtreeRoot));
 20:    } // end if

 22:    // Case 2: rootNode has at most one child
 23:    else if (rootNode.hasRightChild())
 24:       rootNode = rootNode.getRightChild();
 25:    else
 26:       rootNode = rootNode.getLeftChild();

 28:    // Assertion: If rootNode was a leaf, it is now null

 30:    return rootNode;
 31: } // end removeFromRoot