Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Data Structure problem List.java import java.util.Random; import java.util.function.BiFunction; import java.util.function.Function; class EmptyListE extends Exception {} abstract class List { static List singleton (E e) {
Data Structure problem
List.java
import java.util.Random; import java.util.function.BiFunction; import java.util.function.Function; class EmptyListE extends Exception {} abstract class List{ static List singleton (E e) { return new NodeL(e, new EmptyL()); } static List MakeList (Function g, int size) { List result = new EmptyL(); for (int i = 0; i (g.apply(null), result); } return result; } static List MakeIntList (Random r, int bound, int size) { return MakeList(v -> r.nextInt(bound), size); } List push (E elem) { return new NodeL(elem, this); } abstract E getFirst () throws EmptyListE; abstract List getRest () throws EmptyListE; abstract E get (int i) throws EmptyListE; abstract boolean isEmpty (); abstract boolean isSingleton (); abstract int length(); abstract List add (E elem); abstract List append (List other); abstract boolean contains (E e); abstract List drop (int i); abstract List map (Function f); abstract void forEach (Function f); abstract R reduce (R base, BiFunction f); } class EmptyL extends List { E getFirst () throws EmptyListE { throw new EmptyListE(); } List getRest () throws EmptyListE { throw new EmptyListE(); } E get (int i) throws EmptyListE { throw new EmptyListE(); } boolean isEmpty () { return true; } boolean isSingleton () { return false; } int length() { return 0; } List add (E elem) { return new NodeL(elem, this); } List append (List other) { return other; } boolean contains (E e) { return false; } List drop (int i) { return this; } List map (Function f) { return new EmptyL(); } void forEach (Function f) { return; } R reduce (R base, BiFunction f) { return base; } public String toString () { return "#"; } } class NodeL extends List { private E data; private List rest; NodeL(E data, List rest) { this.data = data; this.rest = rest; } E getFirst () { return data; } List getRest () { return rest; } E get (int i) throws EmptyListE { if (i == 0) return data; else return rest.get(i-1); } boolean isEmpty () { return false; } boolean isSingleton () { return rest.isEmpty(); } int length() { return 1 + rest.length(); } List add (E elem) { return new NodeL(data, rest.add(elem)); } List append (List other) { return new NodeL(data, rest.append(other)); } boolean contains (E e) { return data.equals(e) || rest.contains(e); } List drop (int i) { if (i == 0) return this; else return rest.drop(i-1); } List map (Function f) { return new NodeL(f.apply(data), rest.map(f)); } void forEach (Function f) { f.apply(data); rest.forEach(f); } R reduce (R base, BiFunction f) { return f.apply(data,rest.reduce(base,f)); } public String toString () { return data + "," + rest; } }
Tree.java
import java.util.Random; class EmptyTreeE extends Exception {} /** * This hierarcy implements m-ary trees. * An m-ary tree is either empty, or * it is a node with a list of m-subtrees * * The parameter m is often called the branchingFactor * * It is convenient to recognize trees with no children which are * called 'leaves'. Technically an m-leaf is an m-ary tree with * one node and a list of length m of empty subtrees. * * In the three methods makeTree* below, you may assume the incoming * parameter is tuned to create a perfect tree in which every level * has the same number of nodes. So for example for a branching * factor of 3, you can assume the argument n to makeTreeNodes will be * one of: * 0, 1, 1+3, 1+3+9, 1+3+9+27, 1+3+9+27+81, ... * and nothing else. This simplifies your implementation considerably. * We will never test your code with other numbers. * * The Random number generator and bound are used to create the data * at each node: use r.nextInt(bound). We will not assume you are * creating the nodes in any particular order. */ abstract class Tree{ abstract E getData() throws EmptyTreeE; abstract List > getChildren() throws EmptyTreeE; abstract boolean isEmpty(); abstract boolean isLeaf(); abstract int getBranchingFactor(); abstract int getNumberOfNodes(); abstract int numberOfInternalNodes(); abstract int numberOfLeaves(); abstract int getHeight(); static Tree makeLeaf(E elem, int m) { return null; } /* * Assume that 'n' is perfect */ static Tree makeTreeNodes(int n, int m, Random r, int bound) { return null; } static Tree makeTreeInternals(int i, int m, Random r, int bound) { return null; } static Tree makeTreeLeaves(int ell, int m, Random r, int bound) { return null; } } class EmptyT extends Tree { // TODO } class NodeT extends Tree { // TODO } Treetest.java
import org.junit.Test; import java.util.Random; import static org.junit.Assert.*; public class TreeTest { @Test public void emptytree () { Random r = new Random(); Treet1 = Tree.makeTreeNodes(0,2, r, 10); assertEquals(2, t1.getBranchingFactor()); assertEquals(0, t1.getHeight()); assertEquals(0, t1.getNumberOfNodes()); assertTrue(t1.isEmpty()); assertFalse(t1.isLeaf()); assertEquals(0, t1.numberOfInternalNodes()); assertEquals(0, t1.numberOfLeaves()); } @Test public void leaf () { Random r = new Random(); Tree t1 = Tree.makeLeaf(5, 8); assertEquals(8, t1.getBranchingFactor()); assertEquals(1, t1.getHeight()); assertEquals(1, t1.getNumberOfNodes()); assertFalse(t1.isEmpty()); assertTrue(t1.isLeaf()); assertEquals(0, t1.numberOfInternalNodes()); assertEquals(1, t1.numberOfLeaves()); } @Test public void tree1 () { Random r = new Random(); Tree t1; t1 = Tree.makeTreeNodes(1+3+9+27,3,r,10); assertEquals(3, t1.getBranchingFactor()); assertEquals(4, t1.getHeight()); assertEquals(40, t1.getNumberOfNodes()); assertFalse(t1.isEmpty()); assertFalse(t1.isLeaf()); assertEquals(13, t1.numberOfInternalNodes()); assertEquals(27, t1.numberOfLeaves()); t1 = Tree.makeTreeInternals(13,3,r,10); assertEquals(3, t1.getBranchingFactor()); assertEquals(4, t1.getHeight()); assertEquals(40, t1.getNumberOfNodes()); assertFalse(t1.isEmpty()); assertFalse(t1.isLeaf()); assertEquals(13, t1.numberOfInternalNodes()); assertEquals(27, t1.numberOfLeaves()); t1 = Tree.makeTreeLeaves(27,3,r,10); assertEquals(3, t1.getBranchingFactor()); assertEquals(4, t1.getHeight()); assertEquals(40, t1.getNumberOfNodes()); assertFalse(t1.isEmpty()); assertFalse(t1.isLeaf()); assertEquals(13, t1.numberOfInternalNodes()); assertEquals(27, t1.numberOfLeaves()); } }
The requirements are in the java files and picture, exercises and "//TODO" in Tree.java need to be finished, in the end just pass the TreeTest.java
Thank you very much
Definitions. As explained in class, a full binary tree is defined as follows abstract class TreeStep 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