Generic Class Types - Beginning Java - page 594

If the root node is null , the add() method creates a new root node containing the value to be inserted.
If root is not null then the node where it fits in the tree must be found, and this is the function performed
by another version of the add() method that accepts two arguments specifying the value to be inserted into
the tree and the node where it might be inserted. The second argument allows the method to be called re-
cursively. This method can be private as it does not need to be accessed externally. You could implement
it like this:
private void add(T value, Node node) {
int comparison = node.obj.compareTo(value);
if(comparison == 0) { // If value is equal to the current node
++node.count; // just increment the count
return;
}
if(comparison > 0) { // If value less than the current node
if(node.left == null) { // and the left child node is null
node.left = new Node(value); // Store it as the left child node
} else { // Otherwise...
add(value, node.left); // ...call add() again at the left node
}
} else { // It must be greater than the current node
if(node.right == null) { // so it must go to the right...
node.right = new Node(value); // store it as the right node
} else { // ...or when right node is not null
add(value, node.right); // ...call add() again at the right node
}
}
}
This method is called only with a non- null second argument. The first step is to compare the object to
be inserted, which is the first argument, value , with the object stored in the current node, specified by the
second argument, node . If the new object equals the one stored in the current node, you need to update the
count only for the current node.
If the new object is not equal to that stored in the current node, you first check whether it's less. Remem-
ber that the compareTo() method returns a positive integer when the object for which it is called is greater
than the argument, so if the result of a comparison is positive then it means that the argument is less than
that in the current node. That makes it a candidate for the left child node of the current node, but only if the
left child node is null . If the left child node is not null , you call the add() method recursively to add the
object relative to the left node. You've tested for zero and positive values of comparison , so the only other
possibility is that the comparison value is negative. In this case you repeat the same procedure, but with the
right child node. This process finds the place for the new node so that each node has only a left child that
is less than the current node and a right child that is greater. In fact, for any node, the values stored in the
whole left subtree are less than the current node, and the values in the whole right subtree are greater. Now
that you have objects in the tree, you have to figure out how you're going to get them out again.
Extracting Objects from the Binary Tree
Calling the sort() method for a BinaryTree<> object should return a LinkedList<> object containing the
objects from the tree in ascending sequence. The process for selecting the objects to be inserted into the
linked list is also recursive. You can define sort() like this: