A Binary Search Tree Implementation - Data Structures and Abstractions with Java - page 631

< Implementations of contains , getEntry , add , and remove are here. Their definitions appear
in subsequent sections of this chapter. Other methods in SearchTreeInterface are inherited
from BinaryTree . >
. . .

} // end BinarySearchTree

25.6

Disable setTree . Before we go any further, consider the two setTree methods that our class inher-
its from BinaryTree . The client could use these methods to create a tree that, unfortunately, is not a
binary search tree. This outcome would be impossible if the client used SearchTreeInterface to
declare an instance of the tree. For example, if we wrote
SearchTreeInterface<String> dataSet = new BinarySearchTree<String>();
dataSet would not have either of the setTree methods, since they are not in SearchTreeInterface .
But if we wrote
BinarySearchTree<String> dataSet = new BinarySearchTree<String>();
dataSet would have the setTree methods.
To prevent a client from using either version of setTree , we should override these two meth-
ods so that they throw an exception if called. Listing 25-2 shows definitions for these methods that
do just that.

Question 2 The second constructor in the class BinarySearchTree calls the method
setRootNode . Is it possible to replace this call with the call setRootData(rootEntry) ? Explain.

Question 3 Is it necessary to define the methods isEmpty and clear within the class
BinarySearchTree ? Explain.

Searching and Retrieving

25.7

The search algorithm. Segment 23.29 presented the following recursive algorithm to search a
binary search tree:
Algorithm bstSearch(binarySearchTree, desiredObject)
// Searches a binary search tree for a given object.
// Returns true if the object is found.
if (binarySearchTree is empty )
return false
else if (desiredObject == object in the root of binarySearchTree)
return true
else if (desiredObject < object in the root of binarySearchTree)
return bstSearch( left subtree of binarySearchTree, desiredObject)
else
return bstSearch( right subtree of binarySearchTree, desiredObject)

This algorithm is the basis of the method getEntry .

Note: Searching a binary search tree is like performing a binary search of an array: You
search one of two subtrees of the binary search tree instead of searching one of two halves of
an array.