If you are familiar with Java’s Comparable interface (Programming Project 11), then rewrite one of the sorting methods so that it sorts an array of Comparable objects. You may choose selectionsort, insertionsort, mergesort, quicksort, or heapsort. For example, with selectionsort, you would have the specification shown here:

public static void selectionsort
(Comparable[ ] data, int first, int n)
// Precondition: data has at least n non-null
// components starting at data[first], and
// they may all be compared with one another
// using their compareTo methods.
// Postcondition: The elements of data
// have been rearranged so that
// data[first] <= data[first + 1] <= ... <=
// data[first + n - 1].

Data from Project 11

Java has a generic interface called Comparable. A class that implements the Comparable interface must have a method with this specification:

♦ compareTo
public boolean compareTo(E obj)
Compare this object to another object of the same type.

Returns:
The return value is zero if this object is equal to obj; the return value is negative if this object is smaller than obj; the return value is positive if this object is larger than obj.

Throws: ClassCastException
Indicates that obj is the wrong type of object to be compared with this object.

Write a generic class for a bag of Comparable objects, where the objects are stored in a binary search tree. The tree itself should use the BTNode class from Figure 9.10.

The first line of your new bag class should be: 

public class ComparableTreeBag

> 

This tells the Java compiler that the Comparable- TreeBag is a generic class, but that any instantiation of the generic type parameter E must implement the Comparable interface.

Transcribed Image Text:

FIGURE 9.10 Specification and Implementation of the Generic Binary Tree Node Class Generic Class BTNode * public class BTNode from the package edu.colorado.nodes A BTNode provides a node for a binary tree with a reference to an E object as the data in each node. Limitations: Beyond Int. MAX_VALUE elements, treeSize is wrong. Specification Constructor for the BTNode public BTNode(E initialData, BTNode initiallLeft, BTNode initialRight) Initialize a node with specified initial data and links to children. Note that a reference to a child may be null, which indicates that there is no child. Parameters: initialData - the initial data of this new node initialleft and initialRight- references to the children of this new node Postcondition: This new node contains the specified data and links to its children. getData-getLeft-getRight public E getData( ) public BTNode getleft( ) public BTNode getRight( ) These are accessor methods to obtain this node's data or a reference to one of the children. Any of these objects may be null. A null reference to a child indicates that the child does not exist. getLeftmostData public E getleftmostData( ) Accessor method to get the data from the leftmost node of the tree below this node. Returns: The data from the deepest node that can be reached from this node following left links. getRightmostData public E getRightmostData( ) Accessor method to get the data from the rightmost node of the tree below this node. Returns: The data from the deepest node that can be reached from this node following right links.