Java help! Please help complete the min method below in bold. import java.util.Arrays; import java.util.ArrayList; import...
Java help! Please help complete the min method below in bold.
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
/**
* Provides an implementation of a binary search tree
* with no balance constraints, implemented with linked nodes.
*
*
*
*/
public class Bst<T extends Comparable<T>> implements
Iterable<T> {
//////////////////////////////////////////////////////////////////
// I M P L E M E N T T H E M I N M E T H O D B E L O W //
//////////////////////////////////////////////////////////////////
/**
* Returns the smallest element in this binary search tree. If
this
* tree is empty, this method returns null.
*/
public T min() {
}
////////////////////////////////////////////////////////////////////
// D O N O T M O D I F Y B E L O W T H I S P O I N T //
////////////////////////////////////////////////////////////////////
////////////
// Fields //
////////////
// the root of this bst
private Node root;
// the number of nodes in this bst
private int size;
/** Defines the node structure for this bst. */
private class Node {
T element;
Node left;
Node right;
/** Constructs a node containing the given element. */
public Node(T elem) {
element = elem;
}
}
//////////////// //
// Sample driver //
///////////////// /
/** Drives execution. */
public static void main(String[] args) {
Integer[] values = {2, 4, 6, 8, 10};
Collections.shuffle(Arrays.asList(values));
Bst<Integer> bst = new Bst<>();
for (Integer value : values) {
bst.add(value);
}
// should print out 2:
System.out.println(bst.min());
}
////////////////////
// M E T R I C S //
////////////////////
/**
* Returns the number of elements in this bst.
*/
public int size() {
return size;
}
/**
* Returns true if this bst is empty, false otherwise.
*/
public boolean isEmpty() {
return size == 0;
}
/**
* Returns the height of this bst.
*/
public int height() {
return height(root);
}
/**
* Returns the height of node n in this bst.
*/
private int height(Node n) {
if (n == null) {
return 0;
}
int leftHeight = height(n.left);
int rightHeight = height(n.right);
return 1 + Math.max(leftHeight, rightHeight);
}
////////////////////////////////////
// A D D I N G E L E M E N T S //
////////////////////////////////////
/**
* Ensures this bst contains the specified element. Uses an
iterative implementation.
*/
public void add(T element) {
// special case if empty
if (root == null) {
root = new Node(element);
size++;
return;
}
// find where this element should be in the tree
Node n = root;
Node parent = null;
int cmp = 0;
while (n != null) {
parent = n;
cmp = element.compareTo(parent.element);
if (cmp == 0) {
// don't add a duplicate
return;
} else if (cmp < 0) {
n = n.left;
} else {
n = n.right;
}
}
// add element to the appropriate empty subtree of parent
if (cmp < 0) {
parent.left = new Node(element);
} else {
parent.right = new Node(element);
}
size++;
}
/**
* Ensures this bst contains the specified element. Calls a
recursive method.
*/
public void put(T element) {
root = put(element, root);
}
/**
* Ensures this bst contains the specified element. Uses a recursive
implementation.
*/
private Node put(T element, Node n) {
if (n == null) {
size++;
return new Node(element);
}
int cmp = element.compareTo(n.element);
if (cmp < 0) {
n.left = put(element, n.left);
} else if (cmp > 0) {
n.right = put(element, n.right);
}
return n;
}
//////////////////////
// T O S T R I N G //
//////////////////////
/**
* Returns a string representation of the elements in this bst
listed in
* ascending natural order.
*/
@Override
public String toString() {
return inorderList(root).toString();
}
/**
* Returns a List containing the elements of this bst in ascending
natural order.
*/
private List<T> inorderList(Node n) {
List<T> list = new ArrayList<>();
buildInorderList(root, list);
return list;
}
/**
* Builds list from the elements of this bst in ascending natural
order.
*/
private void buildInorderList(Node n, List<T> list) {
if (n != null) {
buildInorderList(n.left, list);
list.add(n.element);
buildInorderList(n.right, list);
}
}
////////////////////////
// I T E R A T I O N //
////////////////////////
/**
* Provides an iterator over the elements in this bst. Elements will
be
* returned in ascending natural order.
*/
@Override
public Iterator<T> iterator() {
return inorderList(root).iterator();
}
}
Homework Answers
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks
// Bst.java
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
/**
* Provides an implementation of a binary search tree with no balance
* constraints, implemented with linked nodes.
*
*
*
*/
public class Bst<T extends Comparable<T>> implements Iterable<T> {
// ////////////////////////////////////////////////////////////////
// I M P L E M E N T T H E M I N M E T H O D B E L O W //
// ////////////////////////////////////////////////////////////////
/**
* Returns the smallest element in this binary search tree. If this tree is
* empty, this method returns null.
*/
public T min() {
// calling the private helper method to find the minimum value
// recursively
return min(root);
}
// helper method to find the smallest value in bst.
private T min(Node node) {
// note: the smallest value in a BST will be the left most value. that
// is the value at the left most node is the smallest value.
// checking if node is null
if (node == null) {
// returning null, because the bst is empty
return null;
}
// if there is a non null left node exists for this node, calling method
// recursively passing left node as paremeter
if (node.left != null) {
return min(node.left);
}
// if the left node is null, then this is the left most node, returning
// the value.
return node.element;
}
// //////////////////////////////////////////////////////////////////
// D O N O T M O D I F Y B E L O W T H I S P O I N T //
// //////////////////////////////////////////////////////////////////
// //////////
// Fields //
// //////////
// the root of this bst
private Node root;
// the number of nodes in this bst
private int size;
/** Defines the node structure for this bst. */
private class Node {
T element;
Node left;
Node right;
/** Constructs a node containing the given element. */
public Node(T elem) {
element = elem;
}
}
// ////////////// //
// Sample driver //
// /////////////// /
/** Drives execution. */
public static void main(String[] args) {
Integer[] values = { 2, 4, 6, 8, 10 };
Collections.shuffle(Arrays.asList(values));
Bst<Integer> bst = new Bst<Integer>();
for (Integer value : values) {
bst.add(value);
}
// should print out 2:
System.out.println(bst.min());
}
// //////////////////
// M E T R I C S //
// //////////////////
/**
* Returns the number of elements in this bst.
*/
public int size() {
return size;
}
/**
* Returns true if this bst is empty, false otherwise.
*/
public boolean isEmpty() {
return size == 0;
}
/**
* Returns the height of this bst.
*/
public int height() {
return height(root);
}
/**
* Returns the height of node n in this bst.
*/
private int height(Node n) {
if (n == null) {
return 0;
}
int leftHeight = height(n.left);
int rightHeight = height(n.right);
return 1 + Math.max(leftHeight, rightHeight);
}
// //////////////////////////////////
// A D D I N G E L E M E N T S //
// //////////////////////////////////
/**
* Ensures this bst contains the specified element. Uses an iterative
* implementation.
*/
public void add(T element) {
// special case if empty
if (root == null) {
root = new Node(element);
size++;
return;
}
// find where this element should be in the tree
Node n = root;
Node parent = null;
int cmp = 0;
while (n != null) {
parent = n;
cmp = element.compareTo(parent.element);
if (cmp == 0) {
// don't add a duplicate
return;
} else if (cmp < 0) {
n = n.left;
} else {
n = n.right;
}
}
// add element to the appropriate empty subtree of parent
if (cmp < 0) {
parent.left = new Node(element);
} else {
parent.right = new Node(element);
}
size++;
}
/**
* Ensures this bst contains the specified element. Calls a recursive
* method.
*/
public void put(T element) {
root = put(element, root);
}
/**
* Ensures this bst contains the specified element. Uses a recursive
* implementation.
*/
private Node put(T element, Node n) {
if (n == null) {
size++;
return new Node(element);
}
int cmp = element.compareTo(n.element);
if (cmp < 0) {
n.left = put(element, n.left);
} else if (cmp > 0) {
n.right = put(element, n.right);
}
return n;
}
// ////////////////////
// T O S T R I N G //
// ////////////////////
/**
* Returns a string representation of the elements in this bst listed in
* ascending natural order.
*/
@Override
public String toString() {
return inorderList(root).toString();
}
/**
* Returns a List containing the elements of this bst in ascending natural
* order.
*/
private List<T> inorderList(Node n) {
List<T> list = new ArrayList<T>();
buildInorderList(root, list);
return list;
}
/**
* Builds list from the elements of this bst in ascending natural order.
*/
private void buildInorderList(Node n, List<T> list) {
if (n != null) {
buildInorderList(n.left, list);
list.add(n.element);
buildInorderList(n.right, list);
}
}
// //////////////////////
// I T E R A T I O N //
// //////////////////////
/**
* Provides an iterator over the elements in this bst. Elements will be
* returned in ascending natural order.
*/
@Override
public Iterator<T> iterator() {
return inorderList(root).iterator();
}
}
/*OUTPUT*/
2
Add Answer to:
Java help! Please help complete the min method below in
bold.
import java.util.Arrays;
import java.util.ArrayList;
import...
Java help: Please help complete the locate method that is in bold.. public class LinkedDoubleEndedList implements...
Java help: Please help complete the locate method that is in bold.. public class LinkedDoubleEndedList implements DoubleEndedList { private Node front; // first node in list private Node rear; // last node in list private int size; // number of elements in list ////////////////////////////////////////////////// // YOU MUST IMPLEMENT THE LOCATE METHOD BELOW // ////////////////////////////////////////////////// /** * Returns the position of the node containing the given value, where * the front node is at position zero and the rear node is...
package hw3; import java.util.LinkedList; /* *********************************************************************** * A simple BST with int keys and no values...
package hw3; import java.util.LinkedList; /* *********************************************************************** * A simple BST with int keys and no values * * Complete each function below. * Write each function as a separate recursive definition (do not use more than one helper per function). * Depth of root==0. * Height of leaf==0. * Size of empty tree==0. * Height of empty tree=-1. * * TODO: complete the functions in this file. * DO NOT change the Node class. * DO NOT change the name...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to com...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to completely test every method in the BST class to ensure the class meets all its requirements. You should read the Listing 25.5: TestBST.java for an idea of what your program should look like. Listing 25.4 BST.java public class BST> extends AbstractTree { protected TreeNode...
1) Extend the Binary Search Tree ADT to include a public method leafCount that returns the...
1) Extend the Binary Search Tree ADT to include
a public method leafCount that returns the number of leaf nodes in
the tree.
2) Extend the Binary Search Tree ADT to include a
public method singleParent-Count that returns the number of nodes
in the tree that have only one child.
3) The Binary search tree ADT is extended to
include a boolean method similarTrees that receives references to
two binary trees and determines whether the shapes of the trees are...
In Java. How would this method look? LinkedBinaryTree.java import java.util.Iterator; public class LinkedBinaryTree implements BinaryTreeADT {...
In Java. How would this method look?
LinkedBinaryTree.java
import java.util.Iterator;
public class LinkedBinaryTree implements BinaryTreeADT {
private BinaryTreeNode root;
/**
* Creates an empty binary tree.
*/
public LinkedBinaryTree() {
root = null;
}
/**
* Creates a binary tree from an existing root.
*/
public LinkedBinaryTree(BinaryTreeNode root) {
this.root = root;
}
/**
* Creates a binary tree with the specified element...
You should now be able to edit the IntTree class. Implement each of the functions labeled...
You should now be able to edit the IntTree class. Implement each of the functions labeled with You are not allowed to use any kind of loop in your solutions. You may not modify the Node class in any way You may not modify the function headers of any of the functions already present in the file. You may not add any fields to the IntTree class. You may not change or remove the line that reads “package hw2;”...
Java: Return an array of booleans in a directed graph. Please complete the TODO section in...
Java: Return an array of booleans in a directed graph. Please complete the TODO section in the mark(int s) function import algs13.Bag; import java.util.HashSet; // See instructions below public class MyDigraph { static class Node { private String key; private Bag<Node> adj; public Node (String key) { this.key = key; this.adj = new Bag<> (); } public String toString () { return key; } public void addEdgeTo (Node n) { adj.add (n); } public Bag<Node> adj () { return adj;...
In Java Language. Modify the LinkedPostionalList class to support a method swap(p,q) that causes the underlying...
In Java Language. Modify the LinkedPostionalList class to support a method swap(p,q) that causes the underlying nodes referenced by positions p and q to be exchanged for each other. Relink the existing nodes, do not create any new nodes. ---------------------------------------------------------------------------------------------------------------------------------------------------------------------- package lists; import java.util.Iterator; import java.util.NoSuchElementException; public class LinkedPositionalList implements PositionalList { //---------------- nested Node class ---------------- /** * Node of a doubly linked list, which stores a reference to its * element and to both the previous and next...
Question B1 You are given the following Java classes: public class Queue { private static class...
Question B1 You are given the following Java classes: public class Queue { private static class Node { Object object; Node next; Node () { object = null; next = null; } Node (Object object, Node next) { this.object = object; this.next = next; private Node header; private int size = 0; // size shows the no of elements in queue public Object dequeue () { if (size == 0 ) { return null; else { Object remove_object = header.object;...
Write a client method that returns a count of the number of nodes in a binary...
Write a client method that returns a count of the number of
nodes in a binary search tree that contain scores less than or
equal to a passed-in argument (parameter) value. The method header
is:
int countLowerScores (BinarySearchTree tree, int maxValue)
The BinarySearchTree contains these methods in the
picture.
public class BinarySearchTreecT> implements BSTInterfacecT> //reference to the root of this BST public BSTNode<T> root; public Comparator<T> comp: IIused for all comparisons public boolean found: / used by remove public BinarYSearchTree()...
1) Extend the Binary Search Tree ADT to include
a public method leafCount that returns the number of leaf nodes in
the tree.
2) Extend the Binary Search Tree ADT to include a
public method singleParent-Count that returns the number of nodes
in the tree that have only one child.
3) The Binary search tree ADT is extended to
include a boolean method similarTrees that receives references to
two binary trees and determines whether the shapes of the trees are...
In Java. How would this method look?
LinkedBinaryTree.java
import java.util.Iterator;
public class LinkedBinaryTree implements BinaryTreeADT {
private BinaryTreeNode root;
/**
* Creates an empty binary tree.
*/
public LinkedBinaryTree() {
root = null;
}
/**
* Creates a binary tree from an existing root.
*/
public LinkedBinaryTree(BinaryTreeNode root) {
this.root = root;
}
/**
* Creates a binary tree with the specified element...
Question B1 You are given the following Java classes: public class Queue { private static class Node { Object object; Node next; Node () { object = null; next = null; } Node (Object object, Node next) { this.object = object; this.next = next; private Node header; private int size = 0; // size shows the no of elements in queue public Object dequeue () { if (size == 0 ) { return null; else { Object remove_object = header.object;...
Write a client method that returns a count of the number of
nodes in a binary search tree that contain scores less than or
equal to a passed-in argument (parameter) value. The method header
is:
int countLowerScores (BinarySearchTree tree, int maxValue)
The BinarySearchTree contains these methods in the
picture.
public class BinarySearchTreecT> implements BSTInterfacecT> //reference to the root of this BST public BSTNode<T> root; public Comparator<T> comp: IIused for all comparisons public boolean found: / used by remove public BinarYSearchTree()...
Most questions answered within 3 hours.
-
Perform the following calculation. Make sure to pay attention to
significant figures. Your answer should be...
asked 2 minutes ago -
10. Net Present Value
Method and Internal Rate of Return Method for a service company
Buckeye...
asked 2 minutes ago -
An air conditioner removes hot air at 35 °C and 70 % relative
humidity from the...
asked 3 minutes ago -
TRUE OR FALSE :if false please explain
protiens folds up according to thermodynamic principles into a...
asked 5 minutes ago -
Of the 28 restaurants in an area, 4 serve on one type of
cuisine, 9 serve...
asked 20 minutes ago -
Which of the following is FALSE for catabolic pathways?
They are oxidative.
They generate oxidized enzyme...
asked 35 minutes ago -
Question 3 (20 Marks)
Read the text below and answer the question
accordingly.
ABC Enterprises Cc...
asked 42 minutes ago -
How does computer technology such as patient portals
affects revenue and expenses in a healthcare
environment?
asked 43 minutes ago -
what is the most stable chair conformation for beta -
D - Mannose
asked 44 minutes ago -
Use the definition of the fact that f(x) is O(g(x)) to
show that:
1. 7x^2 is...
asked 45 minutes ago -
In view of the fact that so many marriages end in divorce, why
do you think...
asked 1 hour ago -
You are an entrepreneur starting a biotechnology firm. If your
research is successful, the technology can...
asked 1 hour ago