Revise BST in Listing 25.5, using a generic parameter and a Comparator for comparing objects. Define a new constructor with a Comparator as its argument as follows:BST(Comparator comparator)

Listing

Transcribed Image Text:

1 public class BST> extends AbstractTree { protected TreeNode root; protected int size = 0; 2 3 4. 5 /** Create a default binary search tree */ public BST() { 8 10 /** Create a binary search tree from an array of objects */ public BST(E[] objects) { for (int i = 0; i < objects.length; i++) insert(objects[i]); 11 12 13 14 15 @Override /** Return true if the element is in the tree */ public boolean search(E e) { TreeNode current = root; // Start from the root 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 while (current != nul1) { if (e.compareTo(current.element) < 0) { current = current.left; else if (e.compareTo(current.element) > 0) { current = current.right; else // element matches current.element return true; // Element is found return false; 34 @Override /** Insert element e into the binary search tree. * Return true if the element is inserted successfully. * / public boolean insert(E e) { if (root == null) root = createNewNode (e); // Create a new root else { // Locate the parent node TreeNode parent = null; TreeNode current = root; while (current != null) if (e.compareTo(current.element) < 0) { parent = current; current = current.left; 35 36 37 38 39 40 41 42 43 44 45 46 47 else if (e.compareTo(current.element) > 0) { parent = current; current = current.right; 48 49 50 51 52 else 53 return false; // Duplicate node not inserted 54 // Create the new node and attach it to the parent node if (e.compareTo(parent.element) < 0) parent.left = createNewNode (e); else parent.right = createNewNode (e); 55 56 57 58 59 60 61 62 size++; return true; // Element inserted successfully 63 64 65 66 protected TreeNode createNewNode(E e) { return new TreeNode<>(e); 67 68 69 @Override /** Inorder traversal from the root */ public void inorder() { inorder(root); 70 71 72 73 74 75 /** Inorder traversal from a subtree */ protected void inorder (TreeNode root) { if (root == null) return; inorder(root.left); System.out.print(root.element + " "); inorder(root.ri ght); 76 77 78 79 80 81 82 83 @Override /** Postorder traversal from the root */ public void postorder() { postorder(root); 84 85 86 87 88 /** Postorder traversal from a subtree */ protected void preorder(TreeNode root) { if (root -- null) return; postorder(root.left); postorder(root.right); System.out.print(root.element + " "); 89 90 91 92 93 94 95 96 @Override /** Preorder traversal from the root */ public void preorder() { preorder(root); 97 98 99 100 101 /** Preorder traversal from a subtree */ protected void postorder(TreeNode root) { if (root == nul1) return; System.out.print(root.element + " "); preorder (root.left); preorder(root.right); 102 103 104 105 106 107 108 109 110 111 112 113 /** This inner class is static, because it does not access any instance members defined in its outer class */ public static class TreeNode» { protected E element; protected TreeNode left;