Create a new project and class BinarySort with the following structure: public c
ID: 668508 • Letter: C
Question
Create a new project and class BinarySort with the following structure:
public class BinarySort {
/**
* Returns the given numbers in ascending sorted order
*/
public static List<Integer> sort(List<Integer> numbers);
}
You can sort these numbers using a binary tree, by adding each number to the tree and then reading them out in a certain traversal (either pre-, post- or in-order - think about each one and which would sort the numbers the way you want).
Implement sort() to create a new list of sorted numbers using your binary tree traversal, and then test your method with the following tests:
1.Ensure that an empty list of numbers results in an empty sorted list
2.Ensure that a list of a single number is sorted into a list containing only the same number
3.Ensure that the short input (4,1,5,7,2) is sorted correctly into (1,2,4,5,7)
4.Ensure that the already-sorted input (3,4,5) is correctly sorted into the same list
5.Ensure that the reversed input (5,4,3) is correctly sorted into (3,4,5)
6.Ensure negative numbers are handled correctly, so (4,1) is sorted into (1,4)
Explanation / Answer
BinaryTree.java
import java.util.*;
class BinaryTreeNode {
// member variables
public int value;
public BinaryTreeNode parent;
public BinaryTreeNode left;
public BinaryTreeNode right;
public BinaryTreeNode(int value) {
this.value = value;
this.parent = null;
this.left = null;
this.right = null;
}
}
public class BinaryTree {
// instance variables
public BinaryTreeNode root;
public BinaryTree() {
root = null;
}
public void insertLeft(BinaryTreeNode parent, BinaryTreeNode child) {
parent.left = child;
child.parent = parent;
}
public void insertRight(BinaryTreeNode parent, BinaryTreeNode child) {
parent.right = child;
child.parent = parent;
}
public void insert(int n) {
/* Adding the first root into the binary search tree */
if (root == null) {
root = new BinaryTreeNode(n);
return;
}
BinaryTreeNode current = root;
while (true) {
if (n < current.value) { // goes left
if (current.left == null) { // adds left child of the current node
insertLeft(current, new BinaryTreeNode(n));
return;
}
current = current.left;
}
else if (n > current.value) {
if (current.right == null) {
insertRight(current, new BinaryTreeNode(n));
return;
}
current = current.right;
} else return; // node that is equal to this number
}
}
public boolean contains(int n) {
if (root == null) {
return false;
}
// traversal
BinaryTreeNode current = root;
while (current != null) {
if (n < current.value) {
current = current.left;
} else if (n > current.value) {
current = current.right;
}
else return true; // n is found, i.e equal to current.value
}
// not found
return false;
}
// access methods
public int size() {
return size(root);
}
public boolean isEmpty() {
return (root == null);
}
// extra methods
/* Preoder- visit children and add value, then go left child of the root and then right child of the root */
public List<Integer> preOrderTraversal(BinaryTreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if (root == null) return list;
// visit action of algorithm
list.add(root.value);
// recursive traversal of the children from left to right
if (root.left != null) {
list.addAll(preOrderTraversal(root.left));
}
if (root.right != null) {
list.addAll(preOrderTraversal(root.right));
}
return list;
}
public List<Integer> inOrderTraversal(BinaryTreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if (root == null) return list;
// recursive traversal of the children from left to right
if (root.left != null) {
list.addAll(inOrderTraversal(root.left));
}
// visit action of algorithm
list.add(root.value);
if (root.right != null) {
list.addAll(inOrderTraversal(root.right));
}
return list;
}
public List<Integer> postOrderTraversal(BinaryTreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if (root == null) return list;
// recursive traversal of the children from left to right
if (root.left != null) {
list.addAll(postOrderTraversal(root.left));
}
if (root.right != null) {
list.addAll(postOrderTraversal(root.right));
}
// visit action of the algorithm
list.add(root.value);
return list;
}
private int size(BinaryTreeNode root) {
if (root == null) return 0;
// else there's at least a root
int total = 1;
// recursively accumulates the size of every node
if (root.left != null) {
total += size(root.left);
}
if (root.right != null) {
total += size(root.right);
}
// then returns this total
return total;
}
}
BinarySort.java
import java.util.*;
public class BinarySort {
/**
* Returns the given numbers in ascending order
*/
public static List<Integer> sort(List<Integer> numbers) {
BinaryTree tree = new BinaryTree();
for (Integer i: numbers) { // add numbers from list in order to the binary search tree
tree.insert(i);
}
numbers = tree.inOrderTraversal(tree.root);
return numbers;
}
}
BinarySortTest.java
import static org.junit.Assert.*;
import java.util.ArrayList;
import org.junit.Before;
import org.junit.Test;
import java.util.*;
public class BinarySortTest {
List<Integer> list = new ArrayList<Integer>();
@Test
public void testEmpty() {
List<Integer> expected = new ArrayList<Integer>();
list = BinarySort.sort(list);
assertEquals(expected, list);
}
@Test
public void testSingle() {
list.add(1);
list = BinarySort.sort(list);
List<Integer> expected = new ArrayList<Integer>();
expected.add(1);
assertEquals(expected, list);
}
@Test
public void testSample() {
list.add(4);
list.add(1);
list.add(5);
list.add(7);
list.add(2);
list = BinarySort.sort(list);
List<Integer> expected = new ArrayList<Integer>();
expected.add(1);
expected.add(2);
expected.add(4);
expected.add(5);
expected.add(7);
assertEquals(expected, list);
}
@Test
public void testSortedAlready() {
list.add(3);
list.add(4);
list.add(5);
list = BinarySort.sort(list);
List<Integer> expected = new ArrayList<Integer>();
expected.add(3);
expected.add(4);
expected.add(5);
assertEquals(expected, list);
}
@Test
public void testReverse() {
list.add(5);
list.add(4);
list.add(3);
list = BinarySort.sort(list);
List<Integer> expected = new ArrayList<Integer>();
expected.add(3);
expected.add(4);
expected.add(5);
assertEquals(expected, list);
}
@Test
public void testNegative() {
list.add(4);
list.add(-1);
list = BinarySort.sort(list);
List<Integer> expected = new ArrayList<Integer>();
expected.add(-1);
expected.add(4);
assertEquals(expected, list);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.