Binary search trees - Data Structures and Problem Solving Using Java - page 691

1 package weiss.nonstandard;
2
3 // Basic node stored in unbalanced binary search trees
4 // Note that this class is not accessible outside
5 // this package.
6
7 class BinaryNode<AnyType>
8 {
9 // Constructor
10 BinaryNode( AnyType theElement )
11 {
12 element = theElement;
13 left = right = null;
14 }
15
16 // Data; accessible by other package routines
17 AnyType element; // The data in the node
18 BinaryNode<AnyType> left; // Left child
19 BinaryNode<AnyType> right; // Right child
20 }

figure 19.5
The BinaryNode class
for the binary search
tree

1 package weiss.nonstandard;
2
3 // BinarySearchTree class
4 //
5 // CONSTRUCTION: with no initializer
6 //
7 // ******************PUBLIC OPERATIONS*********************
8 // void insert( x ) --> Insert x
9 // void remove( x ) --> Remove x
10 // void removeMin( ) --> Remove minimum item
11 // Comparable find( x ) --> Return item that matches x
12 // Comparable findMin( ) --> Return smallest item
13 // Comparable findMax( ) --> Return largest item
14 // boolean isEmpty( ) --> Return true if empty; else false
15 // void makeEmpty( ) --> Remove all items
16 // ******************ERRORS********************************
17 // Exceptions are thrown by insert, remove, and removeMin if warranted
18
19 public class BinarySearchTree<AnyType extends Comparable<? super AnyType>>
20 {
21 public BinarySearchTree( )
22 { root = null; }
23
24 public void insert( AnyType x )
25 { root = insert( x, root ); }

figure 19.6a
The BinarySearchTree class skeleton ( continues )