1: // Removes an entry from the tree rooted at a given node. 2: // rootNode is a reference to the root of a tree. 3: // entry is the object to be removed. 4: // oldEntry is an object whose data field is null. 5: // Returns the root node of the resulting tree; if entry matches 6: // an entry in the tree, oldEntry's data field is the entry 7: // that was removed from the tree; otherwise it is null. 8: private BinaryNode<T> removeEntry(BinaryNode<T> rootNode, T entry, 9: ReturnObject oldEntry) 10: { 11: if (rootNode != null) 12: { 13: T rootData = rootNode.getData(); 14: int comparison = entry.compareTo(rootData); 15: 16: if (comparison == 0) // entry == root entry 17: { 18: oldEntry.set(rootData); 19: rootNode = removeFromRoot(rootNode); 20: } 21: else if (comparison < 0) // entry < root entry 22: { 23: BinaryNode<T> leftChild = rootNode.getLeftChild(); 24: BinaryNode<T> subtreeRoot = removeEntry(leftChild, entry, oldEntry); 25: rootNode.setLeftChild(subtreeRoot); 26: } 27: else // entry > root entry 28: { 29: BinaryNode<T> rightChild = rootNode.getRightChild(); 30: rootNode.setRightChild(removeEntry(rightChild, entry, oldEntry)); 31: } // end if 32: } // end if 33: 34: return rootNode; 35: } // end removeEntry 36: // Version 4.0