BINARY SEARCH TREES - Introduction to Java Programming: Comprehensive Version - page 940

174
175 // Case 1: current has no left child
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

Case 1

reconnect parent

reconnect parent

Case 2

locate parentOfRightMost
locate rightMost

replace current

reconnect
parentOfRightMost

reduce size
successful deletion

return true ; // Element deleted successfully

213 }
214
215 @Override /** Obtain an iterator. Use inorder. */
216

public java.util.Iterator<E> iterator() { iterator

217 return new InorderIterator();

218 }
219
220 // Inner class InorderIterator

221 private class InorderIterator implements java.util.Iterator<E> {

iterator class

222 // Store the elements in a list

223 private java.util.ArrayList<E> list = internal list

224 new java.util.ArrayList<>();

225 private int current = 0 ; // Point to the current element in list current position

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);

obtain inorder list