Java Reference
In-Depth Information
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 follow-
ing box.
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.)
binary search
tree
A tree that satisfies the Binary Search Tree Storage Rule is referred to as a
binary
search tree
.
Note that if a tree satisfies the Binary Search Tree Storage Rule and you output the
values using the Inorder Processing method, then the numbers will be output in order
from smallest to largest.
For trees that follow the Binary Search Tree Storage Rule and that are short and fat
rather than tall and thin, values can be very quickly retrieved from the tree using a binary
search algorithm that is similar in spirit to the binary search algorithm we presented in
Display 11.6. The topic of searching and maintaining a binary storage tree to realize this
efficiency is a large topic that goes beyond what we have room for here. However, we
give one example of a class for trees that satisfy the Binary Search Tree Storage Rule.
EXAMPLE:
A Binary Search Tree Class
★
Display 15.40 contains the definition of a class for a binary search tree that satisfies the
Binary Search Tree Storage Rule. For simplicity, this tree stores integers, but a routine
modification can produce a similar tree class that stores objects of any class that imple-
ments the
Comparable
interface. Display 15.41 demonstrates the use of this tree class.
Note that no matter in which order the integers are inserted into the tree, the output,
which uses inorder traversal, outputs the integers in sorted order.
(continued on page 868)
