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