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