Java Reference
In-Depth Information
The term
tree
may seem like a misnomer. The root is at the top of the tree, and the
branching structure looks more like a root branching structure than a tree branching
structure. The secret to the terminology is to turn the picture (Display 15.39) upside
down. The picture then does resemble the branching structure of a tree, and the root
node is where the tree's root would begin. The nodes at the ends of the branches
with both link instance variables set to
null
are known as
leaf nodes
, a terminology
that may now make some sense. By analogy to an empty linked list, an
empty tree
is
denoted by setting the link variable
root
equal to
null
.
Note that a tree has a recursive structure. Each tree has, in effect, two subtrees whose
root nodes are the nodes pointed to by the
leftLink
and
rightLink
of the root node.
These two subtrees are circled in Display 15.39. This natural recursive structure makes
trees particularly amenable to recursive algorithms. For example, consider the task of
searching the tree in such a way that you visit each node and do something with the
data in the node (such as writing it out to the screen). There is a general plan of attack
that goes as follows:
leaf node
empty tree
Preorder Processing
1. Process the data in the root node.
2. Process the left subtree.
3. Process the right subtree.
Obtain a number of variants on this search process by varying the order of these
three steps. Two more versions follow:
inorder
Inorder Processing
1. Process the left subtree.
2. Process the data in the root node.
3. Process the right subtree.
Postorder Processing
1. Process the left subtree.
2. Process the right subtree.
3. Process the data in the root node.
The tree in Display 15.39 has numbers that were stored in the tree in a special
way known as the
Binary Search Tree Storage Rule
. The rule is summarized in the
following box.
postorder
Binary Search
Tree Storage
Rule
Binary Search Tree Storage Rule
1. All the values in the left subtree are less than the value in the root node.
2. All the values in the right subtree are greater than or equal to the value in the root node.
3. This rule applies recursively to each of the two subtrees.
(The base case for the recursion is an empty tree, which is always considered to satisfy the rule.)
