This is a java code problem using eclipse, there are two codes below. The purpos
ID: 3846291 • Letter: T
Question
This is a java code problem using eclipse, there are two codes below.
The purpose is to work the BinaryTreeTest code, and get a score of 100.
CODE Below:
import java.util.Arrays;
/**
* A binary search tree for Comparable objects such as Strings, Integers, etc.
* For each node n, all nodes to the left have data which is less than n.data
* and all nodes to the right have data which is greater than n.data.
*
* @param <T>
*/
public class BinaryTree<T extends Comparable<T>> {
private static class Node<T extends Comparable<T>> {
public T data;
public Node<T> left, right;
public void add(T d) {
int comp = d.compareTo(data);
if (comp == 0)
return; // Already in tree
if (comp < 0) {
if (left == null) {
left = new Node<>();
left.data = d;
} else {
left.add(d);
}
} else {
// Greater than
if (right == null) {
right = new Node<>();
right.data = d;
} else {
right.add(d);
}
}
}
public boolean contains(T d) {
int comp = d.compareTo(data);
if (comp == 0)
return true; // Already in tree
if (comp < 0) {
if (left == null) {
return false; // Not in the tree
} else {
return left.contains(d);
}
} else {
if (right == null) {
return false; // Not in the tree
} else {
return right.contains(d);
}
}
}
public void print(int indent) {
if (right != null)
right.print(indent + 1);
char[] spaces = new char[indent * 2];
Arrays.fill(spaces, ' ');
System.out.println(new String(spaces) + data);
if (left != null)
left.print(indent + 1);
}
/**
* The number of nodes of this subtree.
* @return Number of nodes
*/
public int size() {
// We know there is a node here
int total = 1;
// This node may have left children
if (left != null)
total = total + left.size();
// This node may have right children
if (right != null)
total = total + right.size();
// The total size of the tree from this point...
return total;
}
/**
* Delete this node.
*
* @return The new root of this subtree (null if this node had no
* children, also known as a leaf)
*/
public Node<T> deleteNode() {
if (left == null)
return right;
if (right == null)
return left;
Node<T> successor = right;
if (successor.left == null) {
// Case 1: no left child of immediate successor
right = right.right;
} else {
// Case 2: loop until we find leftmost child
Node<T> successorParent = null;
while (successor.left != null) {
successorParent = successor;
successor = successor.left;
}
successorParent.left = successor.right;
}
// Replace this data with successor data
data = successor.data;
return this;
}
/**
* Deletes the node containing d if it exists.
*
* @param d
* @return A valid BinaryTree that doesn't have d in it but does have
* everything else.
*/
public Node<T> delete(T d) {
int comp = d.compareTo(data);
if (comp == 0)
return deleteNode();
if (comp < 0) {
// If d exists, it's to the left
if (left != null)
left = left.delete(d);
return this;
} else {
if (right != null)
right = right.delete(d);
return this;
}
}
}
private Node<T> root;
public BinaryTree() {
root = null;
}
/**
* Adds data to the tree if it didn't already contain it.
*
* @param data
*/
public void add(T data) {
if (root == null) {
root = new Node<>();
root.data = data;
} else {
root.add(data);
}
}
/**
* Returns true if the tree contains data, false otherwise
*
* @param data
* Does the tree contain this?
* @return true if it does
*/
public boolean contains(T data) {
if (root == null)
return false;
return root.contains(data);
}
/**
* Prints out a representation of the tree (rotate your head 90 degrees
* left)
*/
public void print() {
if (root != null)
root.print(0);
}
/**
* Gets the number of nodes of the tree in O(n) time.
*
* @return number of nodes
*/
public int size() {
if (root == null)
return 0;
return root.size();
}
/**
* Delete the node containing data from the tree, if it exists.
*
* @param data
*/
public void delete(T data) {
root = root.delete(data);
}
/**
* Returns the data value of the node that can reach both a and b in the
* least number of steps. If the tree doesn't contain both a and b, return
* null.
*
* @param a
* @param b
* @return data value
*/
public T reachesBoth(T a, T b) {
// TODO: Implement.
return null;
}
/**
* Among all the nodes which are farthest from the root, find the one which
* is farthest to the right.
*
* @return data value of said node
*/
public T findRightmostLowest() {
// TODO: Implement.
return null;
}
/**
* Return the kth largest element according to the Comparable sorted order
* of the tree. The leftmost node has index 0 and the rightmost node has
* index size() - 1.
*
* @param k
* index
* @return element, or null if k is out of range.
*/
public T findKthLargest(int k) {
// TODO: Implement.
return null;
}
/**
* EXTRA CREDIT: Balance the tree. The new root should be the
* findKthLargest(size()/2) node. Recursively, the root of each subtree
* should also be the size/2-largest node (indexed from 0) of that subtree.
* This method should not call new and should execute in O(n log n) time for
* full credit.
*/
public void balance() {
// TODO: Implement for extra credit.
}
}
TEST CODE Below:
import java.io.ByteArrayOutputStream;
import java.io.PrintStream;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.Arrays;
public class BinaryTreeTest {
public static <T extends Comparable<T>> int reachScore(BinaryTree<T> tree, String name, T first, T second,
T correct, int score) {
if (first instanceof String) {
System.out.println("Testing " + name + ".reachesBoth("" + first + "", "" + second + "")");
} else {
System.out.println("Testing " + name + ".reachesBoth(" + first + ", " + second + ")");
}
T rb = tree.reachesBoth(first, second);
if (correct == rb || (correct != null && correct.equals(rb))) {
System.out.println("Got correct value of " + rb);
return score;
} else {
System.out.println("Expected " + correct + " got " + rb);
return 0;
}
}
public static <T extends Comparable<T>> int rightmostLowestScore(BinaryTree<T> tree, String name, T correct,
int score) {
System.out.println("Testing " + name + ".findRightmostLowest()");
T rb = tree.findRightmostLowest();
if (correct == rb || (correct != null && correct.equals(rb))) {
System.out.println("Got correct value of " + rb);
return score;
} else {
System.out.println("Expected " + correct + " got " + rb);
return 0;
}
}
public static <T extends Comparable<T>> int kthLargestScore(BinaryTree<T> tree, String name, int k, T correct,
int score) {
System.out.println("Testing " + name + ".findKthLargest(" + k + ")");
T rb = tree.findKthLargest(k);
if (correct == rb || (correct != null && correct.equals(rb))) {
System.out.println("Got correct value of " + rb);
return score;
} else {
System.out.println("Expected " + correct + " got " + rb);
return 0;
}
}
public static void main(String[] args) throws NoSuchAlgorithmException {
int reachesBothScore = 0, findRightmostLowestScore = 0, findKthLargestScore = 0;
int ecScore = 0;
try {
String[] letters = { "M", "G", "N", "D", "H", "B", "F" };
BinaryTree<String> letterTree = new BinaryTree<>();
for (String name : letters) {
letterTree.add(name);
}
BinaryTree<String> emptyTree = new BinaryTree<>();
BinaryTree<String> simpleTree = new BinaryTree<>();
simpleTree.add("Hello");
reachesBothScore += reachScore(letterTree, "letterTree", "B", "H", "G", 2);
reachesBothScore += reachScore(letterTree, "letterTree", "F", "N", "M", 2);
reachesBothScore += reachScore(letterTree, "letterTree", "B", "D", "D", 2);
reachesBothScore += reachScore(letterTree, "letterTree", "X", "M", null, 2);
reachesBothScore += reachScore(letterTree, "letterTree", "N", "N", "N", 2);
reachesBothScore += reachScore(emptyTree, "emptyTree", "a", "b", null, 2);
findRightmostLowestScore += rightmostLowestScore(letterTree, "letterTree", "F", 2);
findRightmostLowestScore += rightmostLowestScore(simpleTree, "simpleTree", "Hello", 2);
findKthLargestScore += kthLargestScore(letterTree, "letterTree", 1, "D", 2);
findKthLargestScore += kthLargestScore(letterTree, "letterTree", 4, "H", 2);
findKthLargestScore += kthLargestScore(letterTree, "letterTree", -1, null, 2);
findKthLargestScore += kthLargestScore(letterTree, "letterTree", 7, null, 2);
letterTree.add("P");
findRightmostLowestScore += rightmostLowestScore(letterTree, "letterTree", "F", 2);
letterTree.add("O");
findRightmostLowestScore += rightmostLowestScore(letterTree, "letterTree", "O", 2);
BinaryTree<Integer> intTree = new BinaryTree<>();
int[] rightLow = { 1, -56981709, -113963419, -95375583, -95375583, -105278602, -86690766, -86690766,
-96593785, -96593785 };
Integer[] kthLarge = { null, 2081208021, 47078692, -652853260, -1078997883, -1277215666, -1410985124,
-1524948544, -1590615071, -1667402819 };
for (int i = 1, j = 0; j <= 1000; i += 101 * 101 * 101 * 101, j++) {
intTree.add(i);
if (j <= 900 && j % 100 == 0) {
findRightmostLowestScore += rightmostLowestScore(intTree, j + " element containing intTree",
rightLow[j / 100], 2);
findKthLargestScore += kthLargestScore(intTree, j + " element containing intTree", 100,
kthLarge[j / 100], 2);
}
}
// If you have trouble, you may want to take a look at the tree!
// intTree.print();
reachesBothScore += reachScore(intTree, "intTree", 460883892, 356823491, 416241605, 2);
reachesBothScore += reachScore(intTree, "intTree", -2102232259, -2110917076, -2109698874, 2);
reachesBothScore += reachScore(intTree, "intTree", 2146874548, -2140626133, 1, 2);
reachesBothScore += reachScore(intTree, "intTree", -1958559782, -2034129328, -2005638473, 2);
reachesBothScore += reachScore(intTree, "intTree", 2128286712, 94157383, 104060402, 2);
reachesBothScore += reachScore(intTree, "intTree", -276223732, -1770245018, -1693457270, 2);
reachesBothScore += reachScore(intTree, "intTree", 1816105509, 1116173557, 1144664412, 2);
reachesBothScore += reachScore(intTree, "intTree", 3, 4, null, 2);
findRightmostLowestScore += rightmostLowestScore(intTree, "intTree", -96593785, 2);
findKthLargestScore += kthLargestScore(intTree, "intTree", 700, 851071045, 2);
findKthLargestScore += kthLargestScore(intTree, "intTree", 600, 434829441, 2);
findKthLargestScore += kthLargestScore(intTree, "intTree", 500, 18587837, 2);
findKthLargestScore += kthLargestScore(intTree, "intTree", 400, -408774988, 2);
findKthLargestScore += kthLargestScore(intTree, "intTree", 300, -843604428, 2);
findKthLargestScore += kthLargestScore(intTree, "intTree", 1000, 2146874548, 2);
findKthLargestScore += kthLargestScore(intTree, "intTree", 0, -2140626133, 2);
System.out.println("Now testing extra credit balance method (please make sure you haven't modified the print method)...");
PrintStream out = System.out;
try {
ByteArrayOutputStream bs = new ByteArrayOutputStream();
letterTree.balance();
System.setOut(new PrintStream(bs));
letterTree.print();
System.setOut(out);
String crunched = bs.toString().replaceAll(" ", "").replaceAll(" ", "");
if (crunched.equals(" P O N MH G F D B")) {
System.out.println("Rebalanced letter tree OK. Testing int example...");
ecScore++;
bs = new ByteArrayOutputStream();
intTree.balance();
System.setOut(new PrintStream(bs));
intTree.print();
System.setOut(out);
MessageDigest md5 = MessageDigest.getInstance("MD5");
crunched = bs.toString().replaceAll(" ", "").replaceAll(" ", "");
byte[] digest = md5.digest(crunched.getBytes());
if (Arrays.equals(digest, new byte[]{37, -116, 0, -62, 23, -64, -85, -30, 1, 92, 88, 47, -71, 85, -47, 91})) {
System.out.println("Rebalanced int tree OK!");
ecScore++;
} else {
System.out.println("Rebalanced int tree has bad hash: "+Arrays.toString(digest));
int elts = bs.toString().split(" ").length;
if (elts != 1001)
System.out.println("Expected 1001 lines (elements) but saw "+elts);
else System.out.println("Number of elements OK.");
System.out.println("Try some smaller examples. Use the isValid method from class and make sure nothing is dropped from the tree.");
}
} else if (crunched.equals(" P O NM H G F D B")) {
System.out.println("It looks like you didn't implement the balance method. Not testing int tree example.");
} else {
System.out.println("Your rebalanced letter tree looked like this:");
System.out.print(bs.toString());
System.out.println("I expected the rebalanced letter tree to look like this:");
System.out.println(" P O N M H G F D B");
System.out.println("Not testing int tree example.");
}
} finally {
System.setOut(out);
}
} finally {
System.out.println("reachesBoth score " + reachesBothScore + " / 28");
System.out.println("findRightmostLowest score " + findRightmostLowestScore + " / 30");
System.out.println("findKthLargest score " + findKthLargestScore + " / 42");
System.out.println(
"Total: " + (reachesBothScore + findRightmostLowestScore + findKthLargestScore) + " / 100");
if (ecScore > 0)
System.out.println("Extra credit: "+ecScore+" out of 2 examples got expected result (not a final score)");
else System.out.println("You may want to work on the extra credit!");
System.out.println("Score may be affected by academic honesty policy.");
}
}
}
1. Implement public T reachesBoth(T a, T b) You should return the data value of the node that can reach both a and b in the least number of steps (a node can reach itself in 0 steps). If a or b is not in the tree, return null. Consider the Binary Tree String> tree on the left with outputs on the right: tree reaches Both ("B", "H") would return "G tree reaches Both ("F", "N") would return "M" M tree reaches Both("B" D") would return "D tree. reaches Both("X", "M") would return null 2. Implement public T findRightmostLowest() n the above tree, there are two lowest nodes: B and F. Both of them are distance 3 from the root; all other nodes are less than distance 3. F is to the right of B so tree. findRightmostLowest() should return "F" 3. Implement public T findKthLargest(int k) Consider the sorted order of all the elements in the tree. The index of the smallest element is 0. The index of the largest element is tree.size()-1. In the above tree, tree. findKthLargest(1) would return "D" and tree find thLargest (4) would return "H". Return null if k is out of rangeExplanation / Answer
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* A binary search tree for Comparable objects such as Strings, Integers, etc.
* For each node n, all nodes to the left have data which is less than n.data
* and all nodes to the right have data which is greater than n.data.
*
* @param <T>
*/
public class BinaryTree<T extends Comparable<T>> {
private static class Node<T extends Comparable<T>> {
public T data;
public Node<T> left, right;
public void add(T d) {
int comp = d.compareTo(data);
if (comp == 0)
return; // Already in tree
if (comp < 0) {
if (left == null) {
left = new Node<>();
left.data = d;
} else {
left.add(d);
}
} else {
// Greater than
if (right == null) {
right = new Node<>();
right.data = d;
} else {
right.add(d);
}
}
}
public boolean contains(T d) {
int comp = d.compareTo(data);
if (comp == 0)
return true; // Already in tree
if (comp < 0) {
if (left == null) {
return false; // Not in the tree
} else {
return left.contains(d);
}
} else {
if (right == null) {
return false; // Not in the tree
} else {
return right.contains(d);
}
}
}
public void print(int indent) {
if (right != null)
right.print(indent + 1);
char[] spaces = new char[indent * 2];
Arrays.fill(spaces, ' ');
System.out.println(new String(spaces) + data);
if (left != null)
left.print(indent + 1);
}
/**
* The number of nodes of this subtree.
*
* @return Number of nodes
*/
public int size() {
// We know there is a node here
int total = 1;
// This node may have left children
if (left != null)
total = total + left.size();
// This node may have right children
if (right != null)
total = total + right.size();
// The total size of the tree from this point...
return total;
}
/**
* Delete this node.
*
* @return The new root of this subtree (null if this node had no
* children, also known as a leaf)
*/
public Node<T> deleteNode() {
if (left == null)
return right;
if (right == null)
return left;
Node<T> successor = right;
if (successor.left == null) {
// Case 1: no left child of immediate successor
right = right.right;
} else {
// Case 2: loop until we find leftmost child
Node<T> successorParent = null;
while (successor.left != null) {
successorParent = successor;
successor = successor.left;
}
successorParent.left = successor.right;
}
// Replace this data with successor data
data = successor.data;
return this;
}
/**
* Deletes the node containing d if it exists.
*
* @param d
* @return A valid BinaryTree that doesn't have d in it but does have
* everything else.
*/
public Node<T> delete(T d) {
int comp = d.compareTo(data);
if (comp == 0)
return deleteNode();
if (comp < 0) {
// If d exists, it's to the left
if (left != null)
left = left.delete(d);
return this;
} else {
if (right != null)
right = right.delete(d);
return this;
}
}
}
private Node<T> root;
public BinaryTree() {
root = null;
}
/**
* Adds data to the tree if it didn't already contain it.
*
* @param data
*/
public void add(T data) {
if (root == null) {
root = new Node<>();
root.data = data;
} else {
root.add(data);
}
}
/**
* Returns true if the tree contains data, false otherwise
*
* @param data
* Does the tree contain this?
* @return true if it does
*/
public boolean contains(T data) {
if (root == null)
return false;
return root.contains(data);
}
/**
* Prints out a representation of the tree (rotate your head 90 degrees
* left)
*/
public void print() {
if (root != null)
root.print(0);
}
/**
* Gets the number of nodes of the tree in O(n) time.
*
* @return number of nodes
*/
public int size() {
if (root == null)
return 0;
return root.size();
}
/**
* Delete the node containing data from the tree, if it exists.
*
* @param data
*/
public void delete(T data) {
root = root.delete(data);
}
/**
* Returns the data value of the node that can reach both a and b in the
* least number of steps. If the tree doesn't contain both a and b, return
* null.
*
* @param a
* @param b
* @return data value
*/
public T reachesBoth(T a, T b) {
Node<T> t_root = root;
// TODO: Implement.
// if both a & b are present in this tree
if(contains(a) && contains(b)){
while (t_root != null){
// if both a & b are smaller than root, then lca lies in left
int comp_a = a.compareTo(t_root.data);
int comp_b = b.compareTo(t_root.data);
// a and b is lesser then root data
if(comp_a < 0 && comp_b < 0){
t_root = t_root.left;
}
// if both a & b are greater than root data then lca lies in right
else if(comp_a > 0 && comp_b > 0){
t_root = t_root.right;
}
else
break;
}
return t_root.data;
}
// else return null
return null;
}
/**
* Among all the nodes which are farthest from the root, find the one which
* is farthest to the right.
*
* @return data value of said node
*/
public T findRightmostLowest() {
// TODO: Implement.
return null;
}
/**
* Return the kth largest element according to the Comparable sorted order
* of the tree. The leftmost node has index 0 and the rightmost node has
* index size() - 1.
*
* @param k
* index
* @return element, or null if k is out of range.
*/
// ans will store the inorder traversal of the bst
private List<T> ans;
public T findKthLargest(int k) {
// TODO: Implement.
// idea do inorder traversal and get the kth largest element
// c = 0;
// Node<T> node = root;
// return findKthLargestUtil(node, k);
if(k < 0 || k > size()-1){
return null;
}
ans = new ArrayList<T>();
// initially setting node equal to root
Node<T> node = root;
// do the inorder traversal
inOrder(node);
if(ans == null || ans.size() == 0)
return null;
return ans.get(k);
}
// utility function to do inorder traversal
private void inOrder(Node<T> node){
if(node == null){
return;
}
inOrder(node.left);
ans.add(node.data);
inOrder(node.right);
}
/**
* EXTRA CREDIT: Balance the tree. The new root should be the
* findKthLargest(size()/2) node. Recursively, the root of each subtree
* should also be the size/2-largest node (indexed from 0) of that subtree.
* This method should not call new and should execute in O(n log n) time for
* full credit.
*/
public void balance() {
// TODO: Implement for extra credit.
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.