Question
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
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
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
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
TreeNode
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
return new TreeNode<>(e);
}
@Override /** Inorder traversal from the root */
public void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
protected void inorder(TreeNode
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
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
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
public TreeNode
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
return root;
}
/** Returns a path from the root leading to the specified element */
public java.util.ArrayList
java.util.ArrayList
new java.util.ArrayList<>();
TreeNode
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
TreeNode
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
TreeNode
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
return new InorderIterator();
}
// Inner class InorderIterator
private class InorderIterator implements java.util.Iterator
// Store the elements in a list
private java.util.ArrayList
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
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
/** 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
@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;
}
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started