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

Note: Duplicate entries
If you permit duplicate entries in a binary search tree, you can arbitrarily place the duplicate
of an entry in the entry's right subtree. Once you choose the right subtree, you must be con-
sistent. Project 2 at the end of this chapter suggests another strategy for handling duplicates.

Question 1 If you add a duplicate entry Megan to the binary search tree in Figure 25-3 as
a leaf, where should you place the new node?

Beginning the Class Definition

25.5

An outline of the class. Let's begin the definition of a class of binary search trees. Since a binary
search tree is a binary tree, we derive our new class from the class BinaryTree that we defined in
the previous chapter. Thus, we begin our class as indicated in Listing 25-2. Note the call by the
constructor to the protected method setRootNode , which the class inherits from BinaryTree .
Segment 24.9 of the previous chapter contains a definition of setRootNode .

VideoNote

Creating a binary search tree

LISTING 25-2

An outline of the class BinarySearchTree

package TreePackage;
import java.util.Iterator;
public class BinarySearchTree<T extends Comparable<? super T>>
extends BinaryTree<T>
implements SearchTreeInterface<T>

{

public BinarySearchTree()
{

super ();
} // end default constructor

public BinarySearchTree(T rootEntry)
{

super ();
setRootNode( new BinaryNode<T>(rootEntry));
} // end constructor

public void setTree(T rootData) // disable setTree (see Segment 25.6)
{

throw new UnsupportedOperationException();
} // end setTree

public void setTree(T rootData, BinaryTreeInterface<T> leftTree,
BinaryTreeInterface<T> rightTree)

{

throw new UnsupportedOperationException();
} // end setTree