[ Data Structures with Java ] Section 18.2 : STree - A Binary Search Tree Class

Preface : 
We organize the attributes and operations of a binary search tree in a class, called STree, that implements the Collection interface. Using this interface will simplify our use of the class as the implementation structure for the TreeSet and TreeMap data structures. Let us begin by exploring the design of STree class and then using it with several examples. 

STree Design View : 
You are very familiar with the methods in the Collection interface. The STree class places additional stipulations, beyond those inherited from this interface : 

The add() method inserts a new element if a duplicate value is not already present. The boolean return value indicate whether the item was added to the tree.

The class makes use of the fact that an inorder scan visits elements in ascending order. The method toArray() returns an Object array that mirrors the inorder scan and so the elements are referenced in ascending order. An Integer object scans the elements in ascending order.

The STree class has a constructor that creates an empty tree. The method toString() returns a string that describes the elements in a comma-separated list enclose in square brackets. The elements are listed in ascending order. The method first() and last() return the smallest and largest elements in the tree, respectively. For demonstration purpose, we provide the methods displayTree(), drawTree(), and drawTrees() give a "tree-view" of the elements. The methods take an integer argument that satisfies the maximum string length of an element. With drawTrees(), you can see tree updates in successive frames. These are just the display methods we introduced in Chapter 16 for a general binary tree. 
The method find() takes item as an argument and searches the tree looking for an element whose values matches item. The return value is a reference to the value field of the node or null if no match occurs. The find() method allows an application programmer to update an element in the tree without having to remove it and reinsert it back in the tree. 
If we have such a STree class, we can see below example on how to use it : 

- Example 18.2 :

view plaincopy to clipboardprint?

1. public static void main(String args[]) {  
2.     int[] arr = {59, 41, 70, 45, 8, 41, 8, 26, 60};  
3.     boolean isNewElement;  
4.     STree t = new STree();  
5.     for(int i=0; i
6.         isNewElement = t.add(arr[i]);  
7.         if(!isNewElement){System.out.println(arr[i]+" is a duplicate!");}  
8.     }  
9.     System.out.println("The size is "+t.size());  
10.     System.out.println("Maximum/Minimum values: "+t.last().nodeValue+" "+t.first().nodeValue);  
11.     System.out.println("\n"+t);  
12. }  

Output: 

41 is a duplicate!
8 is a duplicate!
The size is 7
Maximum/Minimum values: 70 8

[8, 26, 41, 45, 59, 60, 70]

Supplement : 
* [ Data Structures with Java ] Section 18.1 : Binary Search Trees