Write a Java application program in which main has a BST of Character (using the BTS.java, TREE.java,Tree.java.file, AbstractTree .java). Insert (or create) the BST using the following data: {'j','p','d','f','s','b','n','k','e','w','c','r','g'}. Then display each element using inorder, preorder, and postorder methods. If you want to run this, you may use the BST code files given in a separate link (next to this link) in Catalyst. You don't need to run this so DON'T include the Tree, AbstractTree and BST classes to your submission, only use the BST class in this exercise.

ONLY the main .java file.

BST.java.file

package chapter25;

public class BST>

extends AbstractTree {

protected TreeNode root;

protected int size = 0;

/** Create a default binary tree */

public BST() {

}

/** Create a binary tree from an array of objects */

public BST(E[] objects) {

for (int i = 0; i < objects.length; i++)

insert(objects[i]);

}

@Override /** Returns true if the element is in the tree */

public boolean search(E e) {

TreeNode current = root; // Start from the root

while (current != null) {

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;

}

@Override /** Insert element o into the binary 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;

}

else if (e.compareTo(current.element) > 0) {

parent = current;

current = current.right;

}

else

return false; // Duplicate node not inserted

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

}

size++;

return true; // Element inserted successfully

}

protected TreeNode createNewNode(E e) {

return new TreeNode<>(e);

}

@Override /** Inorder traversal from the root */

public void inorder() {

inorder(root);

}

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

}

@Override /** Postorder traversal from the root */

public void postorder() {

postorder(root);

}

/** Postorder traversal from a subtree */

protected void postorder(TreeNode root) {

if (root == null) return;

postorder(root.left);

postorder(root.right);

System.out.print(root.element + " ");

}

@Override /** Preorder traversal from the root */

public void preorder() {

preorder(root);

}

/** Preorder traversal from a subtree */

protected void preorder(TreeNode root) {

if (root == null) return;

System.out.print(root.element + " ");

preorder(root.left);

preorder(root.right);

}

/** This inner class is static, because it does not access

any instance members defined in its outer class */

public static class TreeNode> {

public E element;

public TreeNode left;

public TreeNode right;

public TreeNode(E e) {

element = e;

}

}

@Override /** Get the number of nodes in the tree */

public int getSize() {

return size;

}

/** Returns the root of the tree */

public TreeNode getRoot() {

return root;

}

/** Returns a path from the root leading to the specified element */

public java.util.ArrayList> path(E e) {

java.util.ArrayList> list =

new java.util.ArrayList<>();

TreeNode current = root; // Start from the root

while (current != null) {

list.add(current); // Add the node to the list

if (e.compareTo(current.element) < 0) {

current = current.left;

}

else if (e.compareTo(current.element) > 0) {

current = current.right;

}

else

break;

}

return list; // Return an array list of nodes

}

@Override /** Delete an element from the binary tree.

* Return true if the element is deleted successfully

* Return false if the element is not in the tree */

public boolean delete(E e) {

// Locate the node to be deleted and also locate its parent node

TreeNode parent = null;

TreeNode current = root;

while (current != null) {

if (e.compareTo(current.element) < 0) {

parent = current;

current = current.left;

}

else if (e.compareTo(current.element) > 0) {

parent = current;

current = current.right;

}

else

break; // Element is in the tree pointed at by current

}

if (current == null)

return false; // Element is not in the tree

// Case 1: current has no left child

if (current.left == null) {

// Connect the parent with the right child of the current node

if (parent == null) {

root = current.right;

}

else {

if (e.compareTo(parent.element) < 0)

parent.left = current.right;

else

parent.right = current.right;

}

}

else {

// Case 2: The current node has a left child

// Locate the rightmost node in the left subtree of

// the current node and also its parent

TreeNode parentOfRightMost = current;

TreeNode rightMost = current.left;

while (rightMost.right != null) {

parentOfRightMost = rightMost;

rightMost = rightMost.right; // Keep going to the right

}

// Replace the element in current by the element in rightMost

current.element = rightMost.element;

// Eliminate rightmost node

if (parentOfRightMost.right == rightMost)

parentOfRightMost.right = rightMost.left;

else

// Special case: parentOfRightMost == current

parentOfRightMost.left = rightMost.left;

}

size--;

return true; // Element deleted successfully

}

@Override /** Obtain an iterator. Use inorder. */

public java.util.Iterator iterator() {

return new InorderIterator();

}

// Inner class InorderIterator

private class InorderIterator implements java.util.Iterator {

// Store the elements in a list

private java.util.ArrayList list =

new java.util.ArrayList<>();

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

public InorderIterator() {

inorder(); // Traverse binary tree and store elements in list

}

/** Inorder traversal from the root*/

private void inorder() {

inorder(root);

}

/** Inorder traversal from a subtree */

private void inorder(TreeNode root) {

if (root == null)return;

inorder(root.left);

list.add(root.element);

inorder(root.right);

}

@Override /** More elements for traversing? */

public boolean hasNext() {

if (current < list.size())

return true;

return false;

}

@Override /** Get the current element and move to the next */

public E next() {

return list.get(current++);

}

@Override /** Remove the current element */

public void remove() {

delete(list.get(current)); // Delete the current element

list.clear(); // Clear the list

inorder(); // Rebuild the list

}

}

/** Remove all elements from the tree */

public void clear() {

root = null;

size = 0;

}

}

Tree.java.file

package chapter25;

public interface Tree extends Iterable {

/** Return true if the element is in the tree */

public boolean search(E e);

/** Insert element o into the binary tree

* Return true if the element is inserted successfully */

public boolean insert(E e);

/** Delete the specified element from the tree

* Return true if the element is deleted successfully */

public boolean delete(E e);

/** Inorder traversal from the root*/

public void inorder();

/** Postorder traversal from the root */

public void postorder();

/** Preorder traversal from the root */

public void preorder();

/** Get the number of nodes in the tree */

public int getSize();

/** Return true if the tree is empty */

public boolean isEmpty();

}

AbstractTree.java.file

package chapter25;

public abstract class AbstractTree implements Tree {

@Override /** Inorder traversal from the root*/

public void inorder() {

}

@Override /** Postorder traversal from the root */

public void postorder() {

}

@Override /** Preorder traversal from the root */

public void preorder() {

}

@Override /** Return true if the tree is empty */

public boolean isEmpty() {

return getSize() == 0;

}

}