Generic Class Types - Beginning Java - page 592

You can come to some general conclusions about what the characteristics of your BinaryTree<T> class are
going to be by considering how it will work. Objects of type Node are going to be a fundamental part of
a binary tree. The Node objects in the tree are really part of the inner workings of the container so they
don't need to be known about or accessible externally. It is therefore appropriate to define Node objects by
a private inner class to the BinaryTree<T> class. All nodes in a binary tree must be different, but you can
allow for duplicates of existing data items to be added to a tree by providing for a count of the number of
identical objects to be recorded within a Node object. As a minimum, a BinaryTree<T> object has to store
the Node object that is the root node for the tree as a member and provide a method for adding new nodes.
Ideally it also provides a means for returning all the data that is stored in the tree in sequence as a single
object, which requires a facility that can package this collection of data. The generic LinkedList<T> type
from the previous example provides a convenient facility for this.
You need to be able to decide whether an object to be stored in a tree is greater or less than existing
objects so bjects that are to be added to the tree must be of a type that has a method for comparing objects.
The java.lang.Comparable<T> interface declares a single method, the compareTo() method, that fits the
bill. The method returns a negative integer if the object for which it is called is less than the argument, 0 if
it equals the argument, and a positive integer if it is greater, so it does precisely what you need for placing
new values in a BinaryTree<T> class object. If you specify the Comparable<T> interface as a constraint on
the type parameter for the BinaryTree<T> class, it ensures that all objects added to a BinaryTree<T> object
are of a class type that implements the compareTo() method. Because Comparable<T> is a parameterized
type, it fits exactly with what you want here.
Here's a first stab at outlining the BinaryTree<T> generic type:
public class BinaryTree<T extends Comparable<T>> {
// Add a value to the tree
public void add(T value) {
// Add a value to the tree...
}
// Create a list containing the values from the tree in sequence
public LinkedList<T> sort() {
// Code to extract objects from the tree in sequence
// and insert them in a LinkedList object and return that...
}
private Node root; // The root node
// Private inner class defining nodes
private class Node {
Node(T value) {
obj = value;
count = 1;
}
T obj; // Object stored in the node
int count; // Count of identical nodes
Node left; // The left child node
Node right; // The right child node
}
}