Question
Hello, I'm using Java on Netbeans. I need help with this practice lab implementation to check if my code is correct and what tweaks need
Hello, I'm using Java on Netbeans. I need help with this practice lab implementation to check if my code is correct and what tweaks need to be make. I'm not well established with writing recursive function in java because I'm used to python so seeing it's implementation helps me learn and I can't find any good tutorial videos that I've found helpful when it comes to applying it to these questions. This is also useful to help me study later on looking back at material. I included all the parts because they are all connected and some are contingent on others. Any help would be greatly appreciated. Thank you very much
Part 1: Insert nodes into a tree
We provided a file BinaryTree.java that defines a class for a binary tree and some methods.
The method insertNode() inserts a node in the leftmost available free spot. That is, if the method is called in the following sequence:
insertNode(50), insertNode(2), insertNode(34), insertNode(19), insertNode(6), then the tree will look like:
And, if we call insertNode(22), the tree will look like:
Notice that the breadth-first traversal order of the resulting tree is the order in which nodes were inserted.
Implement this method using the fields in the constructor. Notice that there is a LinkedList called nodesThatNeedChildren. This List should contain the TreeNodes who are missing 1 or 2 children. Your insert method will use nodesThatNeedChildren to know which TreeNode to add a child to. For example, in the first tree above, nodesThatNeedChildren =
[TreeNode(34),TreeNode(19),TreeNode(6)] and in the second tree, nodesThatNeedChildren = [TreeNode(34),TreeNode(19),TreeNode(6),TreeNode(22)].
When finished, testInsertionAndtoArray test should pass.
Sanity Check:
Does testInsertionAndtoArray pass?
In the test file, call bt.displayTree() to print out the tree as text. Does this tree look like the example above?
Part 2: reduceAtDepth
Write a method that returns the reduced value of the nodes at a given depth. Here, "reduced" starts with
ReduceFunction.initialValue() and combine each element to the total value using
ReduceFunction.combine(). The depth is given as a parameter. If the depth of the tree is actually less than the given height, then return ReduceFunction.initialValue().
Your method must have a running time in O(N), where N is the number of nodes in the tree.
In BinaryTree.java, complete reduceAtDepth() and reduceAtDepthRecurisve(). reduceAtDepthRecurisve() must use recursion and reduceAtDepth() must be iterative (use a loop).
Notice that the generic data types of reduceAtDepthRecurisve() makes the input and output type to be the same type, T. This is just to make the recursion easier.
Notice that there is a signature for a private helper method reduceAtDepthHelper. It has more arguments to facilitate the recursive calls.
Example
If the tree looks like
And the given ReduceFunction is plus (+), then reduceAtDepth(0) is 50, reduceAtDepth(1) is 36 and reduceAtDepth(2) is 25.
Testing
There is one test, sumOfDepthTest, in BinaryTreeTest.java. You must write additional test cases to ensure your code is correct. Your methods will be graded on several additional hidden tests. Some examples of things to test, an empty tree, a tree with only one node, different tree shapes etc.
HINT 1: The provided tests include only one ReduceFunction implementation, IntegerSum. The hidden tests will use other ReduceFunctions, so test your code with other ReduceFunctions that you define.
HINT 2: The provided tests include only BinaryTree
To write a new test case, we recommend that you copy/paste an existing one and change the name of the test method. Then draw your test tree on paper so you know what order to insert nodes using insertNode and what your assertions' expected values are.
Part 3: Queries that use reduceAtDepth
In the queries folder of the project, there is a file named FamilyRecordQuery.java. We created few methods that parses the CSV file of family data and creates a binary tree of the data. Open the CSV file in Excel or in a Text Editor to get a feel for the data. Notice that each level of the tree is a generation of the family. At depth 0 is the child Robert, depth 1 is the parents of Robert, and depth 2 the grandparents and so forth.
Write a method that returns a concatenated string of all the names in a generation separated by one space.
For example, Generation 2: Ryan Jisoon. There is starter code labeled as PART 3. The code queries the treeOfNames by using your ReduceAtDepthRecursive to concatenate names at that depth. For this query, please fix the ConcatenateNames class in FamilyRecordQuery.java.
We've provided the same query below it for the treeOfRecords. It uses your reduceAtDepth to concatenate names of records at that depth. All you need to do is fix the class ConcatenateNamesFromRecord within FamilyRecordQuery.java.
To check your work, use treeOfNames.displayTree() in the main method of FamilyRecordQuery.java and see if the names you printed are correct for the given generation.
Part 4: Select
A "select query" finds the elements that are desired and returns them in depth-first pre-order. Write a method to find the nodes with desired values and return them in a list. To determine what data is desired, we'll use the Predicate interface that is used by filter. Write your method iteratively.
Note that your method must run in linear time: O(n). Implement the method selectIterative.
Example
If the tree contains...
and our predicate is "is the element even?", then the answer will be the list [50,2,6,34]. That is, the preorder traversal is [50,2,19,6,34] but we remove the integers where "is element even?" is false to get [50,2,6,34].
Testing
BinaryTreeTest.java contains a single test case selectIterativeTest. You must write additional test cases for both selectIterative. Notice that selectRecursive is already completed. You are to write test cases for both selectRecursive and selectIterative to make sure the code really works. Your methods will be graded on several additional hidden tests and on the quality of your tests for both methods.
HINT 3: The provided tests include only one Predicate implementation, IsEven. The hidden tests will use other Predicates, so test your code with other Predicates that you define.
To write a new test case, we recommend that you copy/paste an existing one and change the name of the test method. Then draw your test tree on paper so you know what order to insert nodes using insertNode and what your assertions' expected values are.
Part 5: Queries that use Select
In FamilyRecordQuery.java uncomment the code required for Part 5 in the main method and the classes. As you noticed, the family has a lot of people named Robert and a lot of engineers. Use your selectIterative and selectRecursive to find these people in the family tree.
To find all the Roberts, fix the SelectName class and search for the exact string Robert in the name field of the FamilyRecord. This must use selectIterative.
To find all the Engineers, fix the SelectJob class and search for any text containing Engineer in the job field of the FamilyRecord. This must use selectRecursive. This query will output a list of many engineer types (people born in 1920 couldnt have been Software Engineers).
Feel free to test our different names or jobs with these queries. To check your work, look at the displayed tree or the CVS file to see that the output is correct.
Part 6: One more query
Uncomment the code in the main method of FamilyRecordQuery.java. Write the code that will return and print out all the people in the family tree that are under the age of 50. Follow the same structure of the previous queries. You must use selectIterative or selectRecursive to complete this task. Once again, check the CVS file or the displayed tree to see if your output is correct.
Reference Code:
familyRecord.cvs
| Robert | 2024 | Seattle | WA | Student |
| Ryan | 1994 | Arlington Heights | IL | Software Engineer |
| Jisoon | 1995 | Dubuque | IA | Pharmacist |
| Robert | 1963 | Park Ridge | IL | Bio Medical Engineer |
| Angie | 1964 | Park Ridge | IL | Teacher |
| Boge | 1963 | East Dubque | IL | Computer Engineer |
| Jackie | 1970 | Bloomington | IL | Teacher |
| Robert | 1930 | Chicago | IL | Mechanical Engineer |
| Lee | 1932 | Chicago | IL | Homemaker |
| Mathew | 1932 | Chicago | IL | Dentist |
| Sandy | 1936 | Chicago | IL | Teacher |
| David | 1938 | Cedar Falls | IA | Farmer |
| Suki | 1942 | Orange | CA | Shop Owner |
| Michael | 1939 | Chicago | IL | Scientist |
| Amy | 1942 | Chicago | IL | Pharmacist |
| Carl | 1915 | New York | NY | Business |
| Betty | 1920 | Washington | DC | Homemaker |
| John | 1921 | Cedar Rapids | IA | Construction |
| Jane | 1928 | Chicago | IL | Homemaker |
| Peter | 1916 | Fargo | ND | Engineer |
| Stella | 1917 | Bismark | ND | Shop Owner |
| Nick | 1917 | Holmes | OH | Factory Worker |
| Ethal | 1924 | Ames | IA | Programmer |
| Joe | 1922 | Fort Wane | IN | Farmer |
| Mel | 1920 | Green Bay | WI | Chef |
| Mitch | 1919 | Chicago | IL | Inventor |
| Tara | 1911 | Desplaines | IL | Homemaker |
| Ted | 1920 | Vernon Hills | IL | Farmer |
| Tammy | 1918 | Springfield | IL | Seamstress |
| Chris | 1926 | Normal | IL | Farmer |
| Anna | 1925 | Traverse City | MI | Unknown |
Code: BinaryTree.java
package binaryTree;
import iterators.Predicate;
import iterators.ReduceFunction;
import java.util.*;
public class BinaryTree
// the root of the tree
private TreeNode
// the queue of TreeNodes in the tree that have 0 or 1 children
private final List
// number of TreeNodes in the tree
public int size;
public BinaryTree() {
root = null;
nodesThatNeedChildren = new LinkedList();
size = 0;
}
/*
Insert the element d into the BinaryTree at the
"next available location" starting with the left
*/
public void insertNode(T d) {
//PART 1 HERE
}
/* Takes a depth n and a ReduceFunction f
and returns the "combined value" of all elements in the tree at depth n,
where depth=0 is the root.
"combined" means the result of starting with f.initialValue
and "concatentation or combination" each element using f.combine
Requirement: must use a loop
Note on Java syntax: The
type name OutT for use only by this method. This is helpful when the generic
type doesn't hold much meaning for the whole class but is meaningful for a
single method.
*/
public
//PART 2 HERE
return null;
}
/*Takes a depth n and a ReduceFunction f
and returns the "combined value" of all elements in the tree at depth n,
where depth=0 is the root.
"combined" means the result of starting with f.initialValue
and "concatentation or combination" each element using f.combine
NOTE that the "in" generic type and "out" generic type are the same type.
This makes the recurision a easier.
Requirement: must use a recursive.
*/
public T reduceAtDepthRecursive(int n, ReduceFunction
return null;
// replace the above line with the following line, with arguments
// filled in
// return combineValuesHelper(______, ____, ____, _____);
}
private T reduceAtDepthHelper(int depth, TreeNode
//PART 2 HERE
return null;
}
/* Takes a Predicate p and returns the list of all elements
for which p.check is true. The elements must be returned in
"in order" traversal order.
Requirement: must use a loop
*/
public List
//PART 4
return null;
}
/* Takes a Predicate p and returns the list of all elements
for which p.check is true. The elements must be returned in
"in order" traversal order.
Requirement: must be recursive
*/
/*
Requirement: must be recursive
*/
public List
return selectRecursiveHelper(p, root);
}
private List
if(node == null) {
return null;
}
List
if(p.check(node.data)) {
res.add(node.data);
}
if(node.left != null) {
List
for(int i = 0; i
res.add(wantedNodes.get(i));
}
}
if(node.right != null) {
List
for(int i = 0; i
res.add(wantedNodes.get(i));
}
}
return res;
}
//////////////// Dont edit after here //////////////////////
public void printTree() {
Object[] nodeArray = this.toArray();
for (int i = 0; i
System.out.println(nodeArray[i]);
}
}
public void displayTree()
{
Stack globalStack = new Stack
globalStack.push(root);
int emptyLeaf = 32;
boolean isRowEmpty = false;
System.out.println("****..................................................................................................................................****");
while(isRowEmpty==false)
{
Stack localStack = new Stack();
isRowEmpty = true;
for(int j=0; j System.out.print(" "); while(globalStack.isEmpty()==false) { TreeNode temp = (TreeNode) globalStack.pop(); if(temp != null) { System.out.print(temp.data); localStack.push(temp.left); localStack.push(temp.right); if(temp.left != null ||temp.right != null) isRowEmpty = false; } else { System.out.print("--"); localStack.push(null); localStack.push(null); } for(int j=0; j System.out.print(" "); } System.out.println(); emptyLeaf /= 2; while(localStack.isEmpty()==false) globalStack.push( localStack.pop() ); } System.out.println("****..................................................................................................................................****"); } public Object[] toArray() { Object[] r = new Object[size]; if (root == null) { return r; } // traverse the tree to visit all nodes, // adding them to r List frontier.add(root); int soFar = 0; while (frontier.size() > 0) { TreeNode v = (TreeNode) frontier.get(0); r[soFar] = v.data; soFar++; if (v.left != null) { frontier.add(v.left); } if (v.right != null) { frontier.add(v.right); } frontier.remove(0); } return r; } private static class TreeNode public T data; public TreeNode public TreeNode public TreeNode(T d) { data = d; left = null; right = null; } } } Code: BinaryTreeTest.java import iterators.Predicate; import binaryTree.BinaryTree; import iterators.ReduceFunction; import java.util.List; import org.junit.Test; import static org.junit.Assert.*; public class BinaryTreeTest { public BinaryTreeTest() { } @Test public void testInsertionAndtoArray() { BinaryTree bt.insertNode(50); bt.insertNode(2); bt.insertNode(34); bt.insertNode(19); bt.insertNode(6); bt.insertNode(22); Object[] actual = bt.toArray(); Object[] expected = {50, 2, 34, 19, 6, 22}; assertArrayEquals(expected, actual); } @Test public void reduceAtDepthTest() { BinaryTree bt.insertNode(50); bt.insertNode(2); bt.insertNode(34); bt.insertNode(19); bt.insertNode(6); bt.insertNode(22); int sum = bt.reduceAtDepth(2, new IntegerSum()); assertEquals(47, sum); } @Test public void reduceAtDepthTest2() { BinaryTree bt.insertNode(50); bt.insertNode(2); bt.insertNode(34); bt.insertNode(19); bt.insertNode(6); bt.insertNode(22); int sum = bt.reduceAtDepthRecursive(2, new IntegerSum()); assertEquals(47, sum); } @Test public void selectIterativeTest() { BinaryTree bt.insertNode(50); bt.insertNode(2); bt.insertNode(34); bt.insertNode(19); bt.insertNode(6); bt.insertNode(22); Integer[] expected = {50,2,6,34,22}; List assertArrayEquals(expected, answers.toArray()); } // Example implementation of ReduceFunction used by the given test private static class IntegerSum implements ReduceFunction @Override public Integer combine(Integer soFar, Integer x) { return soFar+x; } @Override public Integer initialValue() { return 0; } } // Example implementation of IsEven used by the given test private static class IsEven implements Predicate @Override public boolean check(Integer data) { return data % 2 == 0; } } /* The staff will run your code on several additional JUnit tests of our own. You must write additional tests below to provide more evidence that your method implementations are correct. This test code is part of the assignment, just like the other code. If you write a new test and it fails, GREAT! That means you are making progress. Either the test is wrong and you just need to fix it, or it means you found a bug in your BinaryTree code and now you can go fix it. Don't remove good tests just because they fail. */ // write your new tests below here, using the @Test methods above as an example. // PART 2: testing // PART 4: testing } Code: FamilyRecordQuery,java package queries; import java.util.Iterator; import readers.LineFileReader; import iterators.Apply; import iterators.ApplyFunction; import binaryTree.BinaryTree; import iterators.Predicate; import iterators.ReduceFunction; import java.io.IOException; import java.util.List; public class FamilyRecordQuery { public static void main(String[] args) throws IOException{ Iterator //PART 3 int generationNumberB = 3; String ageGroupB = treeOfNames.reduceAtDepthRecursive(generationNumberB, new ConcatentateNames()); System.out.println("Generation " + generationNumberB + ": " + ageGroupB); int generationNumberA = 4; String ageGroupA = treeOfRecords.reduceAtDepth(3, new ConcatenateNamesFromRecord()); System.out.println("Generation " + generationNumberA + ": " + ageGroupA); //END PART 3 //PART 5 // List //Part 6 // List // //INSERT CODE HERE // System.out.println(under50); } private static class ConcatenateNamesFromRecord implements ReduceFunction private static class ConcatentateNames implements ReduceFunction } //PART 5 START // private static class SelectName implements Predicate //PART 5 END //PART 6 add new class here //////////////// Dont edit after here ////////////////////// // Converts a CSV record from an Object[] to a FlightRecord private static class ConvertToRecord implements ApplyFunction
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
