BINARY SEARCH TREES - Introduction to Java Programming: Comprehensive Version - page 937

16 public boolean isEmpty() { isEmpty implementation

17 return getSize() == 0 ;

18 }
19 }

L ISTING 25.5

BST.java
1 public class BST<E extends Comparable<E>>
2

BST class

extends AbstractTree<E> {

3 protected TreeNode<E> root; root

size

4 protected int size = 0 ;

5
6 /** Create a default binary search tree */
7 public BST() {
8 }
9
10 /** Create a binary search tree from an array of objects */
11 public BST(E[] objects) {
12 for ( int i = 0 ; i < objects.length; i++)
13 insert(objects[i]);
14 }
15
16 @Override /** Return true if the element is in the tree */
17 public boolean search(E e) {
18 TreeNode<E> current = root; // Start from the root
19
20 while (current != null ) {
21 if (e.compareTo(current.element) < 0 ) {
22 current = current.left;
23 }
24 else if (e.compareTo(current.element) > 0 ) {
25 current = current.right;
26 }
27

no-arg constructor

constructor

search

compare objects

else // element matches current.element

28 return true ; // Element is found

29 }
30
31 return false ;

32 }
33
34 @Override /** Insert element e into the binary search tree.
35 * Return true if the element is inserted successfully. */
36 public boolean insert(E e) {
37 if (root == null )
38 root = createNewNode(e); // Create a new root
39 else {
40 // Locate the parent node
41 TreeNode<E> parent = null ;
42 TreeNode<E> current = root;
43 while (current != null )
44 if (e.compareTo(current.element) < 0 ) {
45 parent = current;
46 current = current.left;
47 }
48 else if (e.compareTo(current.element) > 0 ) {
49 parent = current;
50 current = current.right;
51 }
52

insert

new root

compare objects

else

53 return false ; // Duplicate node not inserted