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 }