Generic Class Types - Beginning Java - page 595

public LinkedList<T> sort() {
LinkedList<T>values = new LinkedList<>(); // Create a linked list
treeSort(root); // Sort the objects into the
list
return values;
}
You create a new LinkedList<T> object when the sort() method executes to hold the sorted values
from the tree. The sort() method could be called several times for a BinaryTree<T> object, with the con-
tents of the binary tree being changed in the intervening period, so you must create the linked list from
scratch each time. The real work of inserting the objects from the tree into the linked list, values , is going
to be done by the recursive treeSort() method. You can get an inkling of how this works if you recall that
the left child node object of every node is less than the current node, which is less than the right child node.
Therefore, you want to access the objects in the sequence:
left child node : node : right child node
Of course, the child nodes may themselves have child nodes, but the same applies to them. Take the left
child node, for example. The objects here should be accessed in the sequence:
left child of left child node : left child node : right child of left child node
The same goes for the right child node and its children. All you have to do is express this as code, and
you can do that like this:
private void treeSort(Node node, LinkedList<T> values) {
if(node != null) { // If the current node isn't null
treeSort(node.left, values); // process its left child node
// List the duplicate objects for the current node
for(int i = 0 ; i < node.count ; ++i) {
values.addItem(node.obj);
}
treeSort(node.right, values); // Now process the right child node
}
}
If the node that is passed to the treeSort() method is null , nothing further is left to do so the method
returns. If the argument is not null , you first process the left child node, then the node that was passed as the
argument, and finally the right child node — just as you saw earlier. That does it all. The actual insertion of
an object into the linked list that is passed as the second argument always occurs in the for loop. This loop
typically executes one iteration because most of the time, no duplicate objects are in the tree. The value of
the left child node, if it exists, is always added to the linked list before the value of the current node because
you don't add the value from the current node until the treeSort() method call for the left child returns.
Similarly, the value from the right child node is always added to the linked list after that of the current node.
You're ready to give the generic BinaryTree<T> type a whirl.