Design and write a complete test program to test if the BST class in Listing 25.5 meets all requirements.

Listing

Transcribed Image Text:

1 public class BST> 2 extends AbstractTree { protected TreeNode root; protected int size = 0; 4 5 /** Create a default binary search tree */ public BST() { 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 @0verride /** 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 while (current != null) { if (e.compareTo(current.element) < 0) { current = current.left; 21 22 23 else if (e.compareTo(current.element) > 0) { current = current.right; 24 25 26 27 else // element matches current.element return true; // Element is found 28 29 30 31 return false; 32 33 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 48 49 else if (e.compareTo(current.element) > 0) { parent = current; current = current.right; 50 51 else return false; // Duplicate node not inserted 52 53 54 55 // Create the new node and attach it to the parent node if (e.compareTo(parent.element) < 0) parent.left = createNewNode(e); 56 57 58 else parent.right = createNewNode (e); 59 60 61 62 sizet+; return true; // Element inserted successfully 63 64 65 66 protected TreeNode createNewNode(E e) { return new TreeNode<>(e); 67 68 69 70 @Override /** Inorder traversal from the root */ public void inorder() { inorder(root); 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.right); 76 77 78 79 80 81 82 83 84 85 86 87 88 @Override /** Postorder traversal from the root */ public void postorder() { postorder(root); /** Postorder traversal from a subtree */ protected void preorder(TreeNode root) { if (root == nul1) 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 102 /** 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); 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;