this is in java import java.util.Comparator; public class BinarySearchTree { pri
ID: 3918717 • Letter: T
Question
this is in java
import java.util.Comparator;
public class BinarySearchTree
{
private BinaryNode root = null;
private Comparator comparator;
public BinarySearchTree(Comparator comparator)
{
this.comparator = comparator;
}
public int size()
{
return root == null ? 0 : root.size();
}
private void add(T item, BinaryNode 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 newNode = new BinaryNode();
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 newNode = new BinaryNode();
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();
this.root.setData(item);
}
else
{
add(item, this.root);
}
}
private boolean contains(T item, BinaryNode 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 tree =
new BinarySearchTree(Comparator.naturalOrder());
for (int i = 0; i < 100; i++)
{
tree.add(Math.random());
}
System.out.println(tree);
}
}
this is binary node class
import java.util.Iterator;
public class BinaryNode<T> implements Iterable<T>
{
private T data;
private BinaryNode<T> left;
private BinaryNode<T> right;
public BinaryNode<T> getLeft() { return left; }
public BinaryNode<T> getRight() { return right; }
public T getData() { return data; }
public void setLeft(BinaryNode<T> left) { this.left = left; }
public void setRight(BinaryNode<T> right) { this.right = right; }
public void setData(T data) { this.data = data; }
public String preOrder(String separator)
{
return data
+ (left == null ? "" : separator + left.preOrder(separator))
+ (right == null ? "" : separator + right.preOrder(separator));
}
public String postOrder(String separator)
{
return (left == null ? "" : left.postOrder(separator) + separator)
+ (right == null ? "" : right.postOrder(separator) + separator)
+ data;
}
public String inOrder(String separator)
{
return (left == null ? "" : left.inOrder(separator) + separator)
+ data
+ (right == null ? "" : separator + right.inOrder(separator));
}
public Iterator<T> iterator()
{
return new LevelOrderIterator<T>(this);
}
public int height()
{
return 1 + Math.max(
left == null ? 0 : left.height(),
right == null ? 0 : right.height());
}
public int size()
{
return 1 +
(left == null ? 0 : left.size()) +
(right == null ? 0 : right.size());
}
public T first()
{
return left == null ? data : left.first();
}
public T last()
{
return right == null ? data : right.first();
}
public static void main(String[] args)
{
BinaryNode<Integer> root = new BinaryNode<Integer>();
root.setData(2);
root.setLeft(new BinaryNode<Integer>());
root.getLeft().setData(7);
root.setRight(new BinaryNode<Integer>());
root.getRight().setData(5);
root.getLeft().setLeft(new BinaryNode<Integer>());
root.getLeft().getLeft().setData(2);
root.getLeft().setRight(new BinaryNode<Integer>());
root.getLeft().getRight().setData(6);
root.getRight().setRight(new BinaryNode<Integer>());
root.getRight().getRight().setData(9);
root.getLeft().getRight().setLeft(new BinaryNode<Integer>());
root.getLeft().getRight().getLeft().setData(5);
root.getLeft().getRight().setRight(new BinaryNode<Integer>());
root.getLeft().getRight().getRight().setData(11);
root.getRight().getRight().setLeft(new BinaryNode<Integer>());
root.getRight().getRight().getLeft().setData(4);
System.out.println("Height: " + root.height());
System.out.println("Pre-order: " + root.preOrder(", "));
System.out.println("Post-order: " + root.postOrder(", "));
System.out.println("In-order: " + root.inOrder(", "));
System.out.print("Level-order:");
for (int i : root)
{
System.out.print(" " + i);
}
System.out.println();
}
}
Explanation / Answer
Here is the completed code for this problem. Defined the required method in BinarySearchTree.java. Comments are included, go through it, learn how things work and let me know if you have any doubts. Thanks
// BinarySearchTree.java
import java.util.Arrays;
import java.util.Comparator;
public class BinarySearchTree<T> {
private BinaryNode<T> root = null;
private Comparator<T> comparator;
public BinarySearchTree(Comparator<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);
}
}
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 <T> Object[] treeSort(T[] original, Comparator<T> comp) {
/**
* creating a BST with given comparator
*/
BinarySearchTree<T> bst = new BinarySearchTree<T>(comp);
/**
* Adding all elements of original array to bst
*/
for (int i = 0; i < original.length; i++) {
bst.add(original[i]);
}
/**
* extracting the root element
*/
BinaryNode<T> node = bst.root;
/**
* performing an inorder traversal. Note that your inOrder traversal
* method returns String values seperated by a given seperator. So we
* will need to split it by that seperator, which will yield a String
* array, as the return type is Object[],it does not matter if the
* resultant array is of String type. Or if you have any other method
* for traversing in inorder way, please mention it, I'll make necessary
* changes. Also, you have not provided LevelOrderIterator.java. So I
* dont know if it follows inorder traversal
*/
Object[] sorted = node.inOrder(":").split(":");
return sorted;
}
public static void main(String[] args) {
//testing the sort method using multiple test cases
Integer array[] = new Integer[]{2000, 1, 2, 44, 56, 1233, 1, -8, -33, 74, 6622, 44, 5};
Object[] sorted = BinarySearchTree.treeSort(array, Comparator.naturalOrder());
System.out.println(Arrays.toString(sorted));
String array2[] = new String[]{"Oliver","Felicity","John","Barry"};
sorted = BinarySearchTree.treeSort(array2, Comparator.naturalOrder());
System.out.println(Arrays.toString(sorted));
}
}
/*OUTPUT*/
[-33, -8, 1, 2, 5, 44, 56, 74, 1233, 2000, 6622]
[Barry, Felicity, John, Oliver]
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.