Program Plan:
- Include the required import statement.
- Define the main class.
- Define the main method using public static main.
- Allocate memory to the class “Test”.
- Define the “Test” class.
- Declare the object for the BST.
- Display the initial height of the tree.
- Get the input string from the user.
- Display the height of the tree.
- Call the “breathFirstTraversal” method.
- Create an object and set the string values to that object.
- Again call the “breathFirstTraversal” method.
- Create an integer object for class and set the integer values to that object.
- Display the results.
- Define the “BST” class.
- Declare the required variables.
- Create a default BST class.
- Create a binary tree from an array of objects.
- The “height” method will return the height of the tree.
- Define “breathFirstTraversal” method.
- Declare the linked list.
- Add the values to the list.
- If the list is not empty print the elements.
- If the left node is not null, add the value to the left subtree.
- If the right node is not null, add the value to the right subtree.
- Define the “search” method.
- Start the traverse from the root of the tree.
- If the search element is in the left subtree set that value in “current” variable otherwise set the “current” variable as right subtree value.
- Define the “insert” method.
- If the root is null create the tree otherwise insert the value into left or right subtree.
- Define the “createNewNode”
- Return the result of new node creations.
- Define the “inorder”
- Inorder traverse from the root.
- Define the protected “inorder” method
- Traverse the tree according to the inorder traversal concept.
- Define the “postorder”
- Postorder traverse from the root.
- Define the protected “postorder” method
- Traverse the tree according to the postorder traversal concept.
- Define the “preorder”
- Preorder traverse from the root.
- Define the protected “preorder” method
- Traverse the tree according to the preorder traversal concept.
- Define the “TreeNode” class
- Declare the required variables.
- Define the constructor.
- Define the “getSize” method.
- Return the size.
- Define the “getRoot” method
- Return the root.
- Define the “java.util.ArrayList” method.
- Create an object for the array list.
- If the “current” is not equal to null, add the value to the list.
- If the “current” is less than 0, set the “current” as left subtree element otherwise set the “current” as right subtree element.
- Return the list.
- Define the “delete” method.
- If the “current” is not equal to null, add the value to the list.
- If the “current” is less than 0, delete the “current” as left subtree element otherwise delete the “current” as right subtree element.
- Return the list.
- Define the “iterator” method.
- Call the “inorderIterator” and return the value.
- Define the “inorderIterator”
- Create an object for that method and return the value
- Define the “inorderIterator” class.
- Declare the variables.
- Define the constructor.
- Call the “inorder” method.
- Define the “inorder” method.
- Call the inner “inorder” method with the argument.
- Define the TreeNode “inorder” method.
- If the root value is null return the value, otherwise add the value into the list.
- Define the “hasNext” method
- If the “current” value is less than size of the list return true otherwise return false.
- Define the “next” method
- Return the list.
- Define the “remove” method.
- Call the delete method.
- Clear the list then call the “inorder” method.
- Define the “clear” method
- Set the values to the variables
- Define the interface.
- Declare the required methods.
- Define the required methods.
- Define the main method using public static main.
The below program will add the “breathFirstTraversal” method in the given BST class as follows:
Explanation of Solution
Program:
//import statement
import java.util.*;
//class Test
public class Test
{
// main method
public static void main(String[] args)
{
//allocation of memory
new Test();
}
//definition of "Test"
public Test()
{
//declaration an object of BST
BST<String> tree = new BST<>();
//get the input from the user
System.out.print("The height of tree is " + tree.height());
Scanner input = new Scanner(System.in);
//print the statement
System.out.print("\nEnter strings: ");
//check the condition
for (int i = 0; i < 6; i++)
{
//get the input from the user
String s = input.next();
//insert the value
tree.insert(s.trim());
}
//get the input from the user
System.out.print("\nThe height of tree is " + tree.height());
//insert the value to the tree
tree.insert("Green");
//get the input from the user
System.out.print("\nThe height of tree is " + tree.height());
//print the new line
System.out.println();
//call the "breadthFirstTraversal" method
tree.breadthFirstTraversal();
//create the object for the BST
BST<String> tree1 = new BST<>(new String[]
{"Tom", "George", "Jean", "Jane", "Kevin", "Peter", "Susan",
"Jen", "Kim", "Michael", "Michelle"});
//print the statement
System.out.print("\nThe breadth-first traversal is ");
//call the "breadthFirstTraversal" method
tree1.breadthFirstTraversal();
//get the input from the user
System.out.print("\nThe height of tree1 is " + tree1.height());
//create the object for the BST
BST<Integer> tree2 =
new BST<>(new Integer[]{50, 45, 35, 48, 59, 51, 58});
//print the statement
System.out.print("\nThe breadth-first traversal for tree2 is ");
//call the "breadthFirstTraversal" method
tree2.breadthFirstTraversal();
//get the input from the user
System.out.print("\nThe height of tree2 is " + tree2.height());
}
//definition of "BST" class
public class BST<E extends Comparable<E>> implements Tree<E>
{
//declare the variables
protected TreeNode<E> 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)
{
//check the condition
for (int i = 0; i < objects.length; i++)
//insert the values
insert(objects[i]);
}
// definition of "height"
public int height()
{
//returns the height of this binary tree
return height(root);
}
// definition of "height"
private int height(TreeNode root)
{
//check the condition
if (root == null)
{
//return the value
return -1;
}
else
{
//return the value
return 1 + Math.max(height(root.left), height(root.right));
}
}
// definition of "breadthFirstTraversal" method
public void breadthFirstTraversal()
{
//declaration of linked list
java.util.LinkedList <TreeNode<E>> queue =
new java.util.LinkedList<TreeNode<E>>();
//check the condition
if (root == null)
//return statement
return;
//add the value to the queue
queue.add(root);
//check the condition
while (!queue.isEmpty())
{
//declaration of variable
TreeNode<E> node = queue.removeFirst();
//print the statement
System.out.print (node.element + " ");
//check the condition
if (node.left != null)
//add the value to the queue
queue.add(node.left);
//check the condition
if (node.right != null)
//add the value to the queue
queue.add(node.right);
}
}
//definition of "search" method
public boolean search(E e)
{
//start from the root
TreeNode<E> current = root;
//check the condition
while (current != null)
{
//check the condition
if (e.compareTo(current.element) < 0)
{
//set the value
current = current.left;
}
//check the condition
else if (e.compareTo(current.element) > 0)
{
//set the value
current = current.right;
}
//otherwise
else
//return statement
return true;
}
//return statement
return false;
}
//definition of "insert" method
public boolean insert(E e)
{
//check the condition
if (root == null)
//create a new root
root = createNewNode(e);
//otherwise
else
{
// locate the parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
//check the condition
while (current != null)
//check the condition
if (e.compareTo(current.element) < 0)
{
//set the value
parent = current;
current = current.left;
}
//check the condition
else if (e.compareTo (current.element) > 0)
{
//set the value
parent = current;
current = current.right;
}
//otherwise
else
//return statement
return false;
//check the condition
if (e.compareTo (parent.element) < 0)
//create a new node
parent.left = createNewNode(e);
else
//create a new node
parent.right = createNewNode(e);
}
//increment the size
size++;
//return statement
return true;
}
//definition of "createNewNode"
protected TreeNode<E> createNewNode(E e)
{
//return the statement
return new TreeNode<E>(e);
}
//definition of "inorder"
public void inorder()
{
//inorder traverse from the root
inorder(root);
}
//definition of inorder
protected void inorder(TreeNode<E> root)
{
//check the condition
if (root == null)
//return statement
return;
// inorder traversal from a subtree
inorder(root.left);
//display the element
System.out.print(root.element + " ");
// inorder traversal from a subtree
inorder(root.right);
}
// definition of "postoder"
public void postorder()
{
// postorder traversal from the root
postorder(root);
}
// definition of "postorder"
protected void postorder(TreeNode<E> root)
{
//check the condition
if (root == null)
//return statement
return;
//postorder traversal from a subtree
postorder(root.left);
postorder(root.right);
//display the element
System.out.print(root.element + " ");
}
//definition of "preorder"
public void preorder()
{
// preorder traversal from the root
preorder(root);
}
//definition of "preorder"
protected void preorder(TreeNode<E> root)
{
//check the condition
if (root == null)
//return statement
return;
//display the value
System.out.print(root.element + " ");
// preorder traversal from a subtree
preorder(root.left);
preorder(root.right);
}
//definition of "TreeNode" class
public class TreeNode<E extends Comparable<E>>
{
//declare the variables
E element;
TreeNode<E> left;
TreeNode<E> right;
//definition of constructor
public TreeNode(E e)
{
//set the value
element = e;
}
}
// definition of "getSize" method
public int getSize()
{
//return statement
return size;
}
// definition of "getRoot" method
public TreeNode getRoot()
{
//return statement
return root;
}
// definition of method
public java.util.ArrayList<TreeNode<E>> path(E e)
{
//create an object
java.util.ArrayList<TreeNode<E>> list = new java.util.ArrayList<TreeNode<E>>();
// start from the root
TreeNode<E> current = root;
//check the condition
while (current != null)
{
//add the node to the list
list.add(current);
//check the condition
if (e.compareTo(current.element) < 0)
{
//set the value
current = current.left;
}
//check the condition
else if (e.compareTo(current.element) > 0)
{
//set the value
current = current.right;
}
else
//break statement
break;
}
//return statement
return list;
}
//definition of "delete" method
public boolean delete(E e)
{
// declare the variables
TreeNode<E> parent = null;
TreeNode<E> current = root;
//check the condition
while (current != null)
{
//check the condition
if (e.compareTo(current.element) < 0)
{
//set the value
parent = current;
current = current.left;
}
//check the condition
else if (e.compareTo(current.element) > 0)
{
//set the value
parent = current;
current = current.right;
}
else
//break statement
break;
}
//check the condition
if (current == null)
return false;
//check the condition
if (current.left == null)
{
//check the condition
if (parent == null)
{
//set the value
root = current.right;
}
else
{
//check the condition
if (e.compareTo(parent.element) < 0)
//set the value
parent.left = current.right;
else
//set the value
parent.right = current.right;
}
}
else
{
//set the value
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
//check the condition
while (rightMost.right != null)
{
//set the value
parentOfRightMost = rightMost;
rightMost = rightMost.right;
}
//set the value
current.element = rightMost.element;
//check the condition
if (parentOfRightMost.right == rightMost)
//set the value
parentOfRightMost.right = rightMost.left;
else
//set the value
parentOfRightMost.left = rightMost.left;
}
//decrement the "size"
size--;
//return statement
return true;
}
//definition of "iterator"
public java.util.Iterator<E> iterator()
{
//return statement
return inorderIterator();
}
//definition of "inorderIterator"
public java.util.Iterator<E> inorderIterator()
{
//return statement
return new InorderIterator();
}
// definition of class "InorderIterator"
class InorderIterator implements java.util.Iterator
{
// store the elements in a list
private java.util.ArrayList<E> list = new java.util.ArrayList<E>();
//declare the variable
private int current = 0;
//constructor
public InorderIterator()
{
//call the method
inorder();
}
/*definition of inorder traversal from the root */
private void inorder()
{
//call the method
inorder(root);
}
/*definition of inorder traversal from a subtree */
private void inorder(TreeNode<E> root)
{
//check the condition
if (root == null)
//return statement
return;
//call the method
inorder(root.left);
//add the value to the list
list.add(root.element);
//call the method
inorder(root.right);
}
//definition of "hasNext"
public boolean hasNext()
{
//check the condition
if (current < list.size())
//return statement
return true;
//return statement
return false;
}
//definition of "next" method
public Object next()
{
//return statement
return list.get(current++);
}
// definition of "remove" method
public void remove()
{
//delete the current element
delete(list.get(current));
// clear the list
list.clear();
// rebuild the list
inorder();
}
}
// definition of "clear" method
public void clear()
{
//set the values
root = null;
size = 0;
}
}
//definition of interface
public interface Tree<E> extends java.util.Collection<E>
{
//declaration of methods
public boolean search(E e);
public boolean insert(E e);
public boolean delete(E e);
public int getSize();
// definition of default method
public default void inorder()
{
}
// definition of default method
public default void postorder()
{
}
// definition of default method
public default void preorder()
{
}
// definition of default method
public default boolean isEmpty()
{
//return statement
return size() == 0;
};
@Override
// definition of default method
public default boolean contains(Object e)
{
//return statement
return search((E)e);
}
@Override
// definition of default method
public default boolean add(E e)
{
//return statement
return insert(e);
}
@Override
// definition of default method
public default boolean remove(Object e)
{
//return statement
return delete((E)e);
}
@Override
// definition of default method
public default int size()
{
//return statement
return getSize();
}
@Override
// definition of default method
public default boolean containsAll(Collection<?> c)
{
//return statement
return false;
}
@Override
// definition of default method
public default boolean addAll(Collection<? extends E> c)
{
//return statement
return false;
}
@Override
// definition of default method
public default boolean removeAll(Collection<?> c)
{
//return statement
return false;
}
@Override
// definition of default method
public default boolean retainAll(Collection<?> c)
{
//return statement
return false;
}
@Override
// definition of default method
public default Object[] toArray()
{
//return statement
return null;
}
@Override
// definition of default method
public default <T> T[] toArray(T[] array)
{
//return statement
return null;
}
}
}
The height of tree is -1
Enter strings: aaa
bbb
ccc
ddd
eee
fff
The height of tree is 5
The height of tree is 5
aaa Green bbb ccc ddd eee fff
The breadth-first traversal is Tom George Jean Jane Kevin Jen Peter Kim Susan Michael Michelle
The height of tree1 is 7
The breadth-first traversal for tree2 is 50 45 59 35 48 51 58
The height of tree2 is 3
Want to see more full solutions like this?
Chapter 25 Solutions
Introduction to Java Programming and Data Structures, Comprehensive Version Plus MyProgrammingLab with Pearson EText -- Access Card Package
- Don't use chatgpt or any other AIarrow_forwardGiven a relation schema R = (A, B, C, D, E,G) with a set of functional dependencies F {ABCD BC → DE B→ D D→ A}. (a) Show that R is not in BCNF using the functional dependency A → BCD. (b) Show that AG is a superkey for R (c) Compute a canonical cover Fc for the set of functional dependencies F. Show your work. (d) Give a 3NF decomposition of R based on the canonical cover found in (c). Show your work. (e) Give a BCNF decomposition of R using F. Show your work.arrow_forwardThe following entity-relationship (ER) diagram models a database that helps car deal- ers maintain records of customers and cars in their inventory. Construct a relational database schema from the ER diagram. Your set of schemas should include primary-key and foreign-key constraints and you should ensure there are no redundant schemas. has_model model modelID name vehicle has_vehicle VIN dealer_ID brand name has_available_option has_option has_dealer options options_ID specification dealer dealer ID name customer_ID owned_by customer customer ID namearrow_forward
- A relation schema R = (A, B, C, D, E) with a set of functional dependencies F= {D A CAB} is decomposed into R₁ = (A, B, C) and R2 = (C, D, E). (a) Is this a lossless-join decomposition? Why or why not? (b) Is the decomposition dependency preserving? Why or why not?arrow_forwardNo chatgpt pleasearrow_forwardPlease help draw alu diagraarrow_forward
- 1. Level the resources (R) for the following network. Show exactly which activity is being moved at each cycle and how many days it is being moved. Show all cycles required to utilize the free float and the back float. B H 3 3 L 2 0-0-0 A C F G K N P Q T 0 3 2 2 1 2-2-2 7R 8R 4R 6R 4R 2R 5R 4R D 1 2R 2 M 000 4R 2 4R 1 2 3 4 B5 B BE B 5 5 7 D 2003 C NO C MBSCM В H 5 2 F 7 7 8 SH2F80 5 Н Н 6 7 7L3G4+ 6H2G4 J 4 4 14 8 L K 00 36 9 10 11 12 13 14 15 P 2 Z+ N N 4 4 Z t 2334 4 Σ + M M 4 +arrow_forward2. Perform resource allocation for the following project. Resource limits are 6 labors and 2 helpers. Legend: Activity Dur Resources G H 2 3 2L 1H 2L OH A 1 3L 1H + B D F J K 3 4 6 2 4 4L 2H 3L OH 4L 1H 2L 2H 4L 2H C E 2 2 I 1 2L 1H 3L 1H 5L 1Harrow_forwardNeed Java method please. Thank you.arrow_forward
- Need Java method please. Thank you.arrow_forward3. Write two nested loops to generate the following output. (Note: There is one space between each number, and any extra line shown is intentional.) 12 10 8 6 18 15 12 24 20 30 2 3 3 6 48 12 5 10 15 20 6 12 18 24 30arrow_forwardWrite in verilog coding languagearrow_forward
C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage Learning
Systems ArchitectureComputer ScienceISBN:9781305080195Author:Stephen D. BurdPublisher:Cengage Learning
New Perspectives on HTML5, CSS3, and JavaScriptComputer ScienceISBN:9781305503922Author:Patrick M. CareyPublisher:Cengage Learning
EBK JAVA PROGRAMMINGComputer ScienceISBN:9781337671385Author:FARRELLPublisher:CENGAGE LEARNING - CONSIGNMENT
Programming Logic & Design ComprehensiveComputer ScienceISBN:9781337669405Author:FARRELLPublisher:Cengage