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: Brief Version (11th Global Edition)
- No AI solutions pleasearrow_forwardCreate an original network topology consisting of at least seven routers and twelve links, assigning arbitrary positive weights to each link. Using this topology, apply Dijkstra's Link-State Algorithm to compute the shortest paths from a source router of your choice to all other routers in the network. Your topology must be entirely your own design and should not resemble any examples from the textbook, lecture slides, or other students' work. Al-generated topologies are not permitted. Create a PowerPoint presentation that follows the format and style of slides 11 to 23 from Lecture Slide Set 06 (LS06). You should copy those slides and make any necessary changes, additions, or deletions to reflect your own topology, shortest-path calculations, and update tables. Do not alter the original slide style, layout, or formatting.arrow_forwardCreate an original network topology consisting of at least seven routers and twelve links, assigning arbitrary positive weights to each link. Using this topology, apply Dijkstra's Link-State Algorithm to compute the shortest paths from a source router of your choice to all other routers in the network. Your topology must be entirely your own design and should not resemble any examples from the textbook, lecture slides, or other students' work. Al-generated topologies are not permitted. Createarrow_forward
- x3003 x3008 1110 0000 0000 1100 1110 0010 0001 0000 0101 0100 1010 0000 x3004 0010 0100 0001 0011 x3005 0110 0110 0000 0000 X3006 0110 1000 0100 0000 x3007 0001 0110 1100 0100 0111 0110 0000 What does the following LC-3 program do? Trace Step by Step, SHOW ALL YOUR WORK. x3001 x3002 0000 x3009 0001 0000 0010 0001 X300A 0001 0010 0110 0001 x300B 0001 0100 1011 1111 x300C 0000 0011 1111 1000 X300D 1111 0000 0010 0101 x300E 0000 0000 0000 0101 x300F 0000 0000 0000 0100 x3010 0000 0000 0000 0011 x3011 0000 0000 0000 0110 x3012 0000 0000 0000 0010 x3013 x3014 0000 0000 0000 0000 0000 0100 0000 0111 x3015 0000 0000 0000 0110 x3016 0000 0000 0000 1000 x3017 0000 0000 0000 0111 x3018 0000 0000 0000 0101arrow_forward2) Assume a local area network has four host computers (h1, h2, h3 & h4) and they are connected to the internet through a NAT router (s1). The host computers use private IP address space: 192.168.2/24. Each host is trying to establish 2 TCP connections to a remote webserver through the NAT router. The IP address of the webserver is: 130.12.11.9. Now do the following: 1 a. Assign IP addresses to the interfaces of the hosts and the router. For the router, assign arbitrary addresses. List these addresses. b. Now create a NAT translation table as taught in the class for all TCP connections. Assign arbitrary port numbers as required.arrow_forward1) Consider the following network. Host h6 10.3.0.6 Host h5 10.3.0.5 Host h1 10.1.0.1 OpenFlow controller m 2 3 4 Host h4 10.2.0.4 Host h2 10.1.0.2 Host h3 10.2.0.3 The desired forwarding behavior for the datagrams arriving at s2 is as follows: a) any datagrams arriving on input port 1 from hosts h5 or h6 that are destined to hosts h1 or h2 should be forwarded over output port 2; b) any datagrams arriving on input port 2 from hosts h1 or h2 that are destined to hosts h5 or h6 should be forwarded over output port 1; c) any arriving datagrams on input ports 1 or 2 and destined to hosts h3 or h4 should be delivered to the host specified; d) hosts h3 and h4 should be able to send datagrams to each other. Create a flow table for s2 that implement these forwarding behaviors. Your table should have 2 columns one for match and the other for actions, as taught in the class.arrow_forward
- Based on the last digit of your Kean ID: Create an LC-3 program that compares 3 personally assigned to you numbers stored in memory and finds the maximum of them. Compile and run on https://wchargin.com/lc3web/. Screenshot and explain your result. ID 0 A 7 B с -3 12 1 0 5 -1 Expected max 12 5 2 -8 -2 6 9 My Kean ID: 1233321 3 14 3 6 14 4 -5 -6 -1 -1 сл 5 10 0 4 10 6 2 11 1 11 7 -9 7 -4 7 8 00 66 00 8 5 13 13 9 -2 3 0 3arrow_forward8 9 See the program below that we worked on in class and that multiplies A=4 by B=5, the result 20 is stored in a particular register: Address 15 14 པPy"BI" ༦ དད་པས་ས་་ 12 11 11 10 9 8 7 6 109876543210 13 12 x3000 0 0 0 0 0 1000 000110 x3001 0 0 1 0 0 1 0000 000110 x3002 0 1 0 1 0 1 101 1 100000 x3003 0 0 0 1 0 1 x3004 0 0 0 1 0 101 1 000001 10010 111111 x3005 0 0 0 0 1 01 1 11 1 1 1 1 0 1 x3006 1 1 1 1 0 00000100101 x3007 0 0 0 0 0 00000000101 x3008 0 00 00 0 0000 0000100 Based on the last digit of your Kean ID, you need to modify it to multiply the personally assigned A and B to you and store the result exactly in the register assigned. Write a program in machine language (in binary) so it looks similar to the above. 3 4 ID 0 A 3 B Result Register 6 R4 1 4 7 R5 2 7 3 R6 My Kean ID: 1233321 2 2 00 8 6 5 9 1 6 R7 33 34 R4 6 0 7 R5 55 7 5 5 R6 6 1 12 R7 RR 7 R3 Trace the program/loop step by step and provide the result of your tracing. SHOW ALL YOUR WORK.arrow_forwardYou are tasked with developing a portable system that can be worn to collect health and fitness data. The challenge is to integrate all functions into the smaller form of an ear clip. The device should include heart rate, movement and temperature sensor and wireless communication with a mobile app. Draw a diagram- hardware architecture of the system- including the selection of suitable sensors, communication modules, and an energy-efficient microcontroller. (visualize the components and their connections)arrow_forward
- Draw out an example of 3 systems using Lamport’s logical clock and explain the steps in words.arrow_forward“Systems have become very powerful and sophisticated, providing quality information fordecisions that enable the firm to coordinate both internally and externally.”With reference to the above statement compare the operations of any three data gatheringsystems today’s organisations use to aid decision making.arrow_forwardlabmas Course Home XDocument courses/13810469/menu/a2c41aca-b4d9-4809-ac2e-eef29897ce04 There are three ionizable groups (weak acids and/or bases) in glutamic acid. Label them on the structure below Drag the appropriate labels to their respective targets. OOH [] CH³N CH CH2 CH2 IC HO Reset Helparrow_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