1  /**
  2     This class implements a binary search tree whose
  3     nodes hold objects that implement the Comparable
  4     interface for an appropriate type parameter.
  5  */
  6  public class BinarySearchTree2 <E extends Comparable<? super E>>
  7  {  
  8     private Node root;
  9  
 10     /**
 11        Constructs an empty tree.
 12     */
 13     public BinarySearchTree2()
 14     {  
 15        root = null;
 16     }
 17     
 18     /**
 19        Inserts a new node into the tree.
 20        @param obj the object to insert
 21     */
 22     public void add(E obj) 
 23     {  
 24        Node newNode = new Node();
 25        newNode.data = obj;
 26        newNode.left = null;
 27        newNode.right = null;
 28        if (root == null) { root = newNode; }
 29        else { root.addNode(newNode); }
 30     }
 31  
 32     /**
 33        Tries to find an object in the tree.
 34        @param obj the object to find
 35        @return true if the object is contained in the tree
 36     */
 37     public boolean find(E obj)
 38     {
 39        Node current = root;
 40        while (current != null)
 41        {
 42           int d = current.data.compareTo(obj);
 43           if (d == 0) { return true; }
 44           else if (d > 0) { current = current.left; }
 45           else { current = current.right; }
 46        }
 47        return false;
 48     }
 49     
 50     /**
 51        Tries to remove an object from the tree. Does nothing
 52        if the object is not contained in the tree.
 53        @param obj the object to remove
 54     */
 55     public void remove(E obj)
 56     {
 57        // Find node to be removed
 58  
 59        Node toBeRemoved = root;
 60        Node parent = null;
 61        boolean found = false;
 62        while (!found && toBeRemoved != null)
 63        {
 64           int d = toBeRemoved.data.compareTo(obj);
 65           if (d == 0) { found = true; }
 66           else 
 67           {
 68              parent = toBeRemoved;
 69              if (d > 0) { toBeRemoved = toBeRemoved.left; }
 70              else { toBeRemoved = toBeRemoved.right; }
 71           }
 72        }
 73  
 74        if (!found) { return; }
 75  
 76        // toBeRemoved contains obj
 77  
 78        // If one of the children is empty, use the other
 79  
 80        if (toBeRemoved.left == null || toBeRemoved.right == null)
 81        {
 82           Node newChild;
 83           if (toBeRemoved.left == null) 
 84           {
 85              newChild = toBeRemoved.right;
 86           }
 87           else 
 88           {
 89              newChild = toBeRemoved.left;
 90           }
 91  
 92           if (parent == null) // Found in root
 93           {
 94              root = newChild;
 95           }
 96           else if (parent.left == toBeRemoved)
 97           {
 98              parent.left = newChild;
 99           }
100           else 
101           {
102              parent.right = newChild;
103           }
104           return;
105        }
106        
107        // Neither subtree is empty
108  
109        // Find smallest element of the right subtree
110  
111        Node smallestParent = toBeRemoved;
112        Node smallest = toBeRemoved.right;
113        while (smallest.left != null)
114        {
115           smallestParent = smallest;
116           smallest = smallest.left;
117        }
118  
119        // smallest contains smallest child in right subtree
120           
121        // Move contents, unlink child
122  
123        toBeRemoved.data = smallest.data;
124        if (smallestParent == toBeRemoved) 
125        {
126           smallestParent.right = smallest.right; 
127        }
128        else 
129        {
130           smallestParent.left = smallest.right; 
131        }
132     }
133     
134     /**
135        Prints the contents of the tree in sorted order.
136     */
137     public void inorder(Visitor<? super E> v)
138     {  
139        inorder(root, v);
140     }  
141  
142     /**
143        Prints a node and all of its descendants in sorted order.
144        @param parent the root of the subtree to print
145     */
146     private static <T extends Comparable<? super T>> void 
147        inorder(BinarySearchTree2<T>.Node parent, Visitor<? super T> v)
148     {  
149        if (parent == null) { return; }
150        inorder(parent.left, v);
151        v.visit(parent.data);
152        inorder(parent.right, v);
153     }
154  
155     /**
156        A node of a tree stores a data item and references
157        of the child nodes to the left and to the right.
158     */
159     class Node
160     {  
161        public E data;
162        public Node left;
163        public Node right;
164  
165        /**
166           Inserts a new node as a descendant of this node.
167           @param newNode the node to insert
168        */
169        public void addNode(Node newNode)
170        {  
171           int comp = newNode.data.compareTo(data);
172           if (comp < 0)
173           {  
174              if (left == null) { left = newNode; }
175              else { left.addNode(newNode); }
176           }
177           else if (comp > 0)
178           {  
179              if (right == null) { right = newNode; }
180              else { right.addNode(newNode); }
181           }
182        }
183     }
184  }