Generic Class Types - Beginning Java - page 593

No BinaryTree<T> constructor is defined explicitly because the default constructor suffices. The default
no-arg constructor creates an object with the root node as null . Thus, all objects are added to the tree by
calling the add() method. The sort() method returns a LinkedList<T> object that contain the objects from
the tree in ascending sequence.
The inner Node class has four fields that store the value, the count of the number of identical values in
the current node, and references to its left and right child nodes. The constructor just initializes the obj and
count fields in the Node object that is created, leaving left and right with their default values of null . Of
course, when a Node object is first created, it doesn't have any child nodes, and the count of identical objects
in the tree is 1. Let's look at how objects are inserted into a tree.
Inserting Objects in a Binary Tree
It's easy to see how adding an object to the tree can be a recursive operation in general. The process is illus-
trated in Figure 13-3 .
FIGURE 13-3
The shaded nodes in Figure 13-3 are the ones that have to be considered in the process of inserting the
value 57 in the tree. To find where the new node for an object should be placed in relation to the existing
nodes, you start with the root node to see which of its child nodes represents a potential position for the new
node. If the candidate child node that you choose already exists then you must repeat the process you've just
gone through with the root node with the chosen child node. Of course, this child node may itself have child
nodes so the process may need to be repeated again. You should be able to visualize how this can continue
until either you find a child node that contains an object that is identical to the one contained in the new
node, or you find a vacant child node position where the new node fits.
You can implement the add() method in the BinaryTree<T> class like this:
public void add(T value) {
if(root == null) { // If there's no root node
root = new Node(value); // store it in the root
} else { // Otherwise...
add(value, root); // add it recursively
}
}