1  /**
  2     This class implements a binary search tree whose
  3     nodes hold objects that implement the Comparable
  4     interface.
  5  */
  6  public class BinarySearchTree<E extends Comparable>
  7  {  
  8     private Node root;
  9  
 10     /**
 11        Constructs an empty tree.
 12     */
 13     public BinarySearchTree()
 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<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 void inorder(Node parent, Visitor<E> v)
147     {  
148        if (parent == null) { return; }
149        inorder(parent.left, v);
150        v.visit(parent.data);
151        inorder(parent.right, v);
152     }
153  
154     /**
155        A node of a tree stores a data item and references
156        of the child nodes to the left and to the right.
157     */
158     class Node
159     {  
160        public E data;
161        public Node left;
162        public Node right;
163  
164        /**
165           Inserts a new node as a descendant of this node.
166           @param newNode the node to insert
167        */
168        public void addNode(Node newNode)
169        {  
170           int comp = newNode.data.compareTo(data);
171           if (comp < 0)
172           {  
173              if (left == null) { left = newNode; }
174              else { left.addNode(newNode); }
175           }
176           else if (comp > 0)
177           {  
178              if (right == null) { right = newNode; }
179              else { right.addNode(newNode); }
180           }
181        }
182     }
183  }