Linked Data Structures - Absolute Java - page 881

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 implements 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.
The methods in this class make extensive use of the recursive nature of binary
trees. If aNode is a reference to any node in the tree (including possibly the root
node), then the entire tree with root aNode can be decomposed into three parts:

1. The node aNode .
2. The left subtree with root node aNode.leftLink .
3. The right subtree with root node aNode.rightLink .

The left and right subtrees do themselves satisfy the Binary Search Tree Storage Rule,
so it is natural to use recursion to process the entire tree by doing the following:

1. Processing the left subtree with root node aNode.leftLink
2. Processing the node aNode
3. Processing the right subtree with root node aNode.rightLink

Note that we processed the root node after the left subtree (inorder traversal). This
guarantees that the numbers in the tree are output in the order smallest to largest.
The method showElementsInSubtree uses a very straightforward implementation
of this technique.
Other methods are a bit more subtle in that only one of the two subtrees needs to
be processed. For example, consider the method isInSubtree , which returns true
or false depending on whether or not the parameter item is in the tree with root
node subTreeRoot . To see if the item is anyplace in the tree, set subTreeRoot equal
(continued)