please use java. Thanks. do not need to compile, just write the code. import jav
ID: 3919155 • Letter: P
Question
please use java. Thanks. do not need to compile, just write the code.
import java.util.Comparator;
public class BinarySearchTree<T>
{
private BinaryNode<T> root = null;
private Comparator<? super T> comparator;
public BinarySearchTree(Comparator<? super T> comparator)
{
this.comparator = comparator;
}
public int size()
{
return root == null ? 0 : root.size();
}
private void add(T item, BinaryNode<T> root)
{
if (this.comparator.compare(item, root.getData()) < 0)
{
// Item is less than root:
// add to left subtree
if (root.getLeft() == null)
{
// Base case: opening for a left child
BinaryNode<T> newNode = new BinaryNode<T>();
newNode.setData(item);
root.setLeft(newNode);
}
else
{
// Recursively add to left subtree
add(item, root.getLeft());
}
}
else if (this.comparator.compare(item, root.getData()) > 0)
{
// Item is less than root:
// add to right subtree
if (root.getRight() == null)
{
// Base case: opening for a right child
BinaryNode<T> newNode = new BinaryNode<T>();
newNode.setData(item);
root.setRight(newNode);
}
else
{
// Recursively add to right subtree
add(item, root.getRight());
}
}
// If elements are equal (duplicate), the item is already in the tree
}
public void add(T item)
{
if (this.root == null)
{
this.root = new BinaryNode<T>();
this.root.setData(item);
}
else
{
add(item, this.root);
}
}
public void addRange(T[] array, int first, int last){
if(!(first>last)) {
int mid=(int)((first+last)/2);
add(array[mid]);
addRange(array,first,mid-1);
addRange(array,mid+1,last);
}
else{
return;
}
}
private boolean contains(T item, BinaryNode<T> root)
{
if (this.comparator.compare(item, root.getData()) < 0)
{
// Item is less than root:
// search in left subtree
if (root.getLeft() == null)
{
// Base case: item not found
return false;
}
else
{
// Recursively search in left subtree
return contains(item, root.getLeft());
}
}
else if (this.comparator.compare(item, root.getData()) > 0)
{
// Item is less than root:
// search in right subtree
if (root.getRight() == null)
{
// Base case: item not found
return false;
}
else
{
// Recursively search in right subtree
return contains(item, root.getRight());
}
}
else
{
// Base case: item found
return true;
}
}
public boolean contains(T item)
{
return this.root == null ? false : contains(item, this.root);
}
public String toString()
{
return "[" + (root == null ? "" : root.inOrder(", ")) + "]";
}
public static void main(String[] args)
{
BinarySearchTree<Double> tree =
new BinarySearchTree<Double>(Comparator.naturalOrder());
for (int i = 0; i < 100; i++)
{
tree.add(Math.random());
}
System.out.println(tree);
}
}
3 Tree-Sort In lecture, we discussed a sorting algorithm called Tree-Sort that operates in two steps: . Fill an initially empty binary search tree with the elements of the unsorted list. Perform an in-order traversal of the binary search tree. Using our BinarySearchTree implementation, implement Tree-Sort as a static method with the following signature: public static object[] treeSort (T[] original, Comparator comp) Notice that to avoid issues with instantiating generic arrays, this method can just return an array of type Object, rather than an array of type T. Ifyou've gotten parts 1 and 2 of the lab to work, implementing Tree-Sort should be very simple Write several test cases for Tree-Sort and demonstrate to a TA that they pass.Explanation / Answer
Please find the implementation of Tree sort below.
CODE
=================
public static void inorderRec(Node root, ArrayList<Integer> result){
if (root != null)
{
inorderRec(root.left, result);
result.add(root.getData());
inorderRec(root.right, result);
}
}
public static <T> Object[] treeSort(T[] original, Comparator<T> comp) {
for(int i = 0; i < original.length; i++)
{
add(original[i]);
}
ArrayList<Integer> arr = new ArrayList<Integer>();
inorderRec(root, arr);
Object[] result = new Object[arr.size()];
for(int i=0; i<arr.size(); i++) {
result[i] = arr.get(i);
}
return result;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.