001: /**
002:    This class implements a binary search tree whose
003:    nodes hold objects that implement the Comparable
004:    interface.
005: */
006: public class BinarySearchTree
007: {  
008:    /**
009:       Constructs an empty tree.
010:    */
011:    public BinarySearchTree()
012:    {  
013:       root = null;
014:    }
015:    
016:    /**
017:       Inserts a new node into the tree.
018:       @param obj the object to insert
019:    */
020:    public void add(Comparable obj) 
021:    {  
022:       Node newNode = new Node();
023:       newNode.data = obj;
024:       newNode.left = null;
025:       newNode.right = null;
026:       if (root == null) root = newNode;
027:       else root.addNode(newNode);
028:    }
029: 
030:    /**
031:       Tries to find an object in the tree.
032:       @param obj the object to find
033:       @return true if the object is contained in the tree
034:    */
035:    public boolean find(Comparable obj)
036:    {
037:       Node current = root;
038:       while (current != null)
039:       {
040:          int d = current.data.compareTo(obj);
041:          if (d == 0) return true;
042:          else if (d > 0) current = current.left;
043:          else current = current.right;
044:       }
045:       return false;
046:    }
047:    
048:    /**
049:       Tries to remove an object from the tree. Does nothing
050:       if the object is not contained in the tree.
051:       @param obj the object to remove
052:    */
053:    public void remove(Comparable obj)
054:    {
055:       // Find node to be removed
056: 
057:       Node toBeRemoved = root;
058:       Node parent = null;
059:       boolean found = false;
060:       while (!found && toBeRemoved != null)
061:       {
062:          int d = toBeRemoved.data.compareTo(obj);
063:          if (d == 0) found = true;
064:          else 
065:          {
066:             parent = toBeRemoved;
067:             if (d > 0) toBeRemoved = toBeRemoved.left;
068:             else toBeRemoved = toBeRemoved.right;
069:          }
070:       }
071: 
072:       if (!found) return;
073: 
074:       // toBeRemoved contains obj
075: 
076:       // If one of the children is empty, use the other
077: 
078:       if (toBeRemoved.left == null || toBeRemoved.right == null)
079:       {
080:          Node newChild;
081:          if (toBeRemoved.left == null) 
082:             newChild = toBeRemoved.right;
083:          else 
084:             newChild = toBeRemoved.left;
085: 
086:          if (parent == null) // Found in root
087:             root = newChild;
088:          else if (parent.left == toBeRemoved)
089:             parent.left = newChild;
090:          else 
091:             parent.right = newChild;
092:          return;
093:       }
094:       
095:       // Neither subtree is empty
096: 
097:       // Find smallest element of the right subtree
098: 
099:       Node smallestParent = toBeRemoved;
100:       Node smallest = toBeRemoved.right;
101:       while (smallest.left != null)
102:       {
103:          smallestParent = smallest;
104:          smallest = smallest.left;
105:       }
106: 
107:       // smallest contains smallest child in right subtree
108:          
109:       // Move contents, unlink child
110: 
111:       toBeRemoved.data = smallest.data;
112:       smallestParent.left = smallest.right;
113:    }
114:    
115:    /**
116:       Prints the contents of the tree in sorted order.
117:    */
118:    public void print()
119:    {  
120:       if (root != null)
121:          root.printNodes();
122:    }
123:   
124:    private Node root;
125: 
126:    /**
127:       A node of a tree stores a data item and references
128:       of the child nodes to the left and to the right.
129:    */
130:    private class Node
131:    {  
132:       /**
133:          Inserts a new node as a descendant of this node.
134:          @param newNode the node to insert
135:       */
136:       public void addNode(Node newNode)
137:       {  
138:          if (newNode.data.compareTo(data) < 0)
139:          {  
140:             if (left == null) left = newNode;
141:             else left.addNode(newNode);
142:          }
143:          else
144:          {  
145:             if (right == null) right = newNode;
146:             else right.addNode(newNode);
147:          }
148:       }
149: 
150:       /**
151:          Prints this node and all of its descendants
152:          in sorted order.
153:       */
154:       public void printNodes()
155:       {  
156:          if (left != null)
157:             left.printNodes();
158:          System.out.println(data);
159:          if (right != null)
160:             right.printNodes();
161:       }
162:    
163:       public Comparable data;
164:       public Node left;
165:       public Node right;
166:    }
167: }
168: 
169: 
170: