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

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() {

hasNext in iterator?

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() { get next element

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 }
The insert(E e) method (lines 36-64) creates a node for element e and inserts it into the
tree. If the tree is empty, the node becomes the root. Otherwise, the method finds an appropri-
ate parent for the node to maintain the order of the tree. If the element is already in the tree,
the method returns false ; otherwise it returns true .
The inorder() method (lines 71-81) invokes inorder(root) to traverse the entire
tree. The method inorder(TreeNode root) traverses the tree with the specified root. This
is a recursive method. It recursively traverses the left subtree, then the root, and finally the
right subtree. The traversal ends when the tree is empty.
The postorder() method (lines 84-94) and the preorder() method (lines 97-107) are
implemented similarly using recursion.
The path(E e) method (lines 132-150) returns a path of the nodes as an array list. The
path starts from the root leading to the element. The element may not be in the tree. For
example, in Figure 25.4a, path(45) contains the nodes for elements 60 , 55 , and 45 , and
path(58) contains the nodes for elements 60 , 55 , and 57 .
The implementation of delete() and iterator() (lines 155-269) will be discussed in
Sections 25.3 and 25.5.
Listing 25.6 gives an example that creates a binary search tree using BST (line 4). The
program adds strings into the tree (lines 5-11), traverses the tree in inorder, postorder, and
preorder (lines 14-20), searches for an element (line 24), and obtains a path from the node
containing Peter to the root (lines 28-31).

remove the current

refresh list

clear