Java Reference
In-Depth Information
interesting application of a binary tree is for sorting. This is an easily understood context, so let's use that
to explore how you might implement a generic binary tree class.
Figure 13-2
shows an example of integers
organized in a binary tree structure.
The first node in a binary tree is called the
root node
because this node is the starting point for accessing
all the other nodes in the tree. Each node in a binary tree, including the root node, can have two child nodes,
usually referred to as the
left child node
and the
right child node
. Thus, each node in a binary tree may have
zero, one, or two child nodes.
Figure 13-2
contains examples of all three possibilities. A
parent node
is a
node that has at least one child node and a
leaf node
is a node with no child nodes. The root node is the only
node with no parents.
You can construct a binary tree so that for each node, the object stored as the left child node is always
less than the object stored in the node and the object in the right child node is always greater. With this form
of tree you'll be able to extract the objects that are stored in it so that they are in sequence. The tree shown
in
Figure 13-2
has been constructed like this, and it's a very simple process.
Adding a node involves starting with the root node and seeing whether the new node is less than or greater
than the current node. This establishes whether it is a potential left or right child node for the root node.
If the root node already has a child node in the position where the new node might belong, you repeat the
comparison process with that child node. Eventually you'll find a node that has no child node where the new
node fits, so that's where you put it. Implementing this as a recursive method helps to make the code very
concise.
Given that you have constructed a tree in this manner, starting with the root node you can work your way
through all the nodes in the tree by following the left and right child nodes in an orderly fashion to extract
all the objects from the tree in sequence. Because all the nodes are similar, the use of recursion simplifies
the implementation of this process, too.
Because a binary tree is a structure you can apply to organizing objects of any type, it is an obvious can-
didate for being a generic type. It also provides another example of where being able to constrain the type
parameter is important. The way the tree is constructed implies that you must be able to compare objects
that are added to a tree. This means that every object in the tree must have a method available for comparing
it to objects of the same type. Making the object type implement an interface that declares a method that
compares objects is the way to do this. A binary tree implementation also provides an example of a situation
where you can apply the power of recursion to very good effect.
Defining the Generic Type
