1  public class BST<E extends Comparable<E>> 
  2      extends AbstractTree<E> {
  3    protected TreeNode<E> root;
  4    protected int size = 0;
  5  
  6    /** Create a default binary tree */
  7    public BST() {
  8    }
  9  
 10    /** Create a binary 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 /** Returns 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        else // element matches current.element
 28          return true; // Element is found
 29      }
 30  
 31      return false;
 32    }
 33  
 34    @Override /** Insert element o into the binary 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          else
 53            return false; // Duplicate node not inserted
 54  
 55        // Create the new node and attach it to the parent node
 56        if (e.compareTo(parent.element) < 0)
 57          parent.left = createNewNode(e);
 58        else
 59          parent.right = createNewNode(e);
 60      }
 61  
 62      size++;
 63      return true; // Element inserted
 64    }
 65  
 66    protected TreeNode<E> createNewNode(E e) {
 67      return new TreeNode<E>(e);
 68    }
 69  
 70    @Override /** Inorder traversal from the root*/
 71    public void inorder() {
 72      inorder(root);
 73    }
 74  
 75    /** Inorder traversal from a subtree */
 76    protected void inorder(TreeNode<E> root) {
 77      if (root == null) return;
 78      inorder(root.left);
 79      System.out.print(root.element + " ");
 80      inorder(root.right);
 81    }
 82  
 83    @Override /** Postorder traversal from the root */
 84    public void postorder() {
 85      postorder(root);
 86    }
 87  
 88    /** Postorder traversal from a subtree */
 89    protected void postorder(TreeNode<E> root) {
 90      if (root == null) return;
 91      postorder(root.left);
 92      postorder(root.right);
 93      System.out.print(root.element + " ");
 94    }
 95  
 96    @Override /** Preorder traversal from the root */
 97    public void preorder() {
 98      preorder(root);
 99    }
100  
101    /** Preorder traversal from a subtree */
102    protected void preorder(TreeNode<E> root) {
103      if (root == null) return;
104      System.out.print(root.element + " ");
105      preorder(root.left);
106      preorder(root.right);
107    }
108  
109    /** This inner class is static, because it does not access 
110        any instance members defined in its outer class */
111    public static class TreeNode<E extends Comparable<E>> {
112      protected E element;
113      protected TreeNode<E> left;
114      protected TreeNode<E> right;
115  
116      public TreeNode(E e) {
117        element = e;
118      }
119    }
120  
121    @Override /** Get the number of nodes in the tree */
122    public int getSize() {
123      return size;
124    }
125  
126    /** Returns the root of the tree */
127    public TreeNode<E> getRoot() {
128      return root;
129    }
130  
131    /** Returns a path from the root leading to the specified element */
132    public java.util.ArrayList<TreeNode<E>> path(E e) {
133      java.util.ArrayList<TreeNode<E>> list =
134        new java.util.ArrayList<TreeNode<E>>();
135      TreeNode<E> current = root; // Start from the root
136  
137      while (current != null) {
138        list.add(current); // Add the node to the list
139        if (e.compareTo(current.element) < 0) {
140          current = current.left;
141        }
142        else if (e.compareTo(current.element) > 0) {
143          current = current.right;
144        }
145        else
146          break;
147      }
148  
149      return list; // Return an array of nodes
150    }
151  
152    @Override /** Delete an element from the binary tree.
153     * Return true if the element is deleted successfully
154     * Return false if the element is not in the tree */
155    public boolean delete(E e) {
156      // Locate the node to be deleted and also locate its parent node
157      TreeNode<E> parent = null;
158      TreeNode<E> current = root;
159      while (current != null) {
160        if (e.compareTo(current.element) < 0) {
161          parent = current;
162          current = current.left;
163        }
164        else if (e.compareTo(current.element) > 0) {
165          parent = current;
166          current = current.right;
167        }
168        else
169          break; // Element is in the tree pointed at by current
170      }
171  
172      if (current == null)
173        return false; // Element is not in the tree
174  
175      // Case 1: current has no left children
176      if (current.left == null) {
177        // Connect the parent with the right child of the current node
178        if (parent == null) {
179          root = current.right;
180        }
181        else {
182          if (e.compareTo(parent.element) < 0)
183            parent.left = current.right;
184          else
185            parent.right = current.right;
186        }
187      }
188      else {
189        // Case 2: The current node has a left child
190        // Locate the rightmost node in the left subtree of
191        // the current node and also its parent
192        TreeNode<E> parentOfRightMost = current;
193        TreeNode<E> rightMost = current.left;
194  
195        while (rightMost.right != null) {
196          parentOfRightMost = rightMost;
197          rightMost = rightMost.right; // Keep going to the right
198        }
199  
200        // Replace the element in current by the element in rightMost
201        current.element = rightMost.element;
202  
203        // Eliminate rightmost node
204        if (parentOfRightMost.right == rightMost)
205          parentOfRightMost.right = rightMost.left;
206        else
207          // Special case: parentOfRightMost == current
208          parentOfRightMost.left = rightMost.left;     
209      }
210  
211      size--;
212      return true; // Element inserted
213    }
214  
215    @Override /** Obtain an iterator. Use inorder. */
216    public java.util.Iterator<E> iterator() {
217      return new InorderIterator();
218    }
219  
220    // Inner class InorderIterator
221    private class InorderIterator implements java.util.Iterator<E> {
222      // Store the elements in a list
223      private java.util.ArrayList<E> list =
224        new java.util.ArrayList<E>();
225      private int current = 0; // Point to the current element in list
226  
227      public InorderIterator() {
228        inorder(); // Traverse binary tree and store elements in list
229      }
230  
231      /** Inorder traversal from the root*/
232      private void inorder() {
233        inorder(root);
234      }
235  
236      /** Inorder traversal from a subtree */
237      private void inorder(TreeNode<E> root) {
238        if (root == null)return;
239        inorder(root.left);
240        list.add(root.element);
241        inorder(root.right);
242      }
243  
244      @Override /** More elements for traversing? */
245      public boolean hasNext() {
246        if (current < list.size())
247          return true;
248  
249        return false;
250      }
251  
252      @Override /** Get the current element and move to the next */
253      public E next() {
254        return list.get(current++);
255      }
256  
257      @Override /** Remove the current element */
258      public void remove() {
259        delete(list.get(current)); // Delete the current element
260        list.clear(); // Clear the list
261        inorder(); // Rebuild the list
262      }
263    }
264  
265    /** Remove all elements from the tree */
266    public void clear() {
267      root = null;
268      size = 0;
269    }
270  }