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(); Tree t1 = 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 Tree class Empty extends Tree extends Tree E data; Tree left, right; Empty trees will not count as nodes. A leaf is a node with empty trees as children. A node that is not a leaf is called an internal node. A tree is called an m-ary tree if every internal node has no more than m children. The tree is called a full m-ary tree if every internal node has exactly m children. For example, consider the following trees BC D E E FG H K L M The tree on the left is a full 2-ary tree: it has 5 nodes, 3 of them D, E, and C are leaves and two of them A and B are internal nodes. In other words, we have m 2, l = 3, 2, and n 5. The tree on the right is a full 3-ary tree: it has 13 nodes, 9 leaves, and 4 internal nodes Proofs. To prove a property P of binary trees, the general recipe is . Prove P(Empty) . Assume P(t) and P(t2) hold for an arbitrary trees t and t2 and prove P(Node d ti t2) for the larger tree produced by attaching the subtrees ti and t2 to a node with data d This establishes that for every tree t, we have P(t). Sometimes the statement to prove is only valid for trees that have at least one node. In that case, the first case above is to prove P(Node d Empty Empty) for a leaf containing data d. Example Let's prove that a full binary with n nodes has 1 leaves. The statement is not true for an empty tree, so we will try to prove it for n >1. Let N(t) be the number of nodes for a tree t and L(t) be the number of leaves for a tree t. Formally we want to prove that for every non-empty tree L(t) - . Base case: t has one node, i.e., N(t) = 1, We want to prove that L(t)-N(2+1 = I. There are two constructors for trees. Since the tree is not empty, it must have been constructed using the constructor for nodes. Since we onlv have one node, it must be a leaf. . Inductive case: the tree t is constructed using Node(d, t1, t2) where t and t2 are two smaller trees with N(h) ni and N(ta)-n2. We have N(t) n + n2+ 1. By induction L(h) = n21 and (t2)-nati. The leaves of t are the leaves of both t1 and tie., L(t) = nit1 + n2+1. We need to prove: N(t) +1 2 L(t) = = nitn2+2-nit1 + n2+1 which is equal to the left hand side Example. Now that we have proved that for non-empty full binary trees L(t) -o+, we can easily write a formula for the number of internal node I(t). Indeed by definition N(t) - I(t) + L(t). So: N(t) 1 2N(t) - N(t)-1 N(t) - 1 I(t) N(t) - L(t) N(t)- 2 2 Exercises 2 Exercises . Prove that a full m-ary with n nodes has (n -1)/m internal nodes and (m -1)n + 1)/m leaves. . Prove that a full m-ary with i internal nodes has mi +1 nodes and (m -1)i 1 leaves. . Prove that a full m-ary with I leaves has (ml -1)/(m-1) nodes and (l - 1)/(m - 1) internal nodes. . Now suppose that someone starts a chain letter. Each person who receives the letter is asked to send it on to four other people. Some people do this, but others do not send any letters. Assume that everyone who forwarded the letter forwarded it to exactly four people and that all the people are distinct. Furthermore, assume that the chain letter ended after 100 people received it but did not send it out. How many people have seen the letter, including the first person? How many people sent out the letter? . Now move on to the starter files and complete the implementation of the Tree class hierarchy. . When you are done submit the solution to the exercises (as a PDF) along with your code to the autograder. Definitions. As explained in class, a full binary tree is defined as follows abstract class Tree class Empty extends Tree extends Tree E data; Tree left, right; Empty trees will not count as nodes. A leaf is a node with empty trees as children. A node that is not a leaf is called an internal node. A tree is called an m-ary tree if every internal node has no more than m children. The tree is called a full m-ary tree if every internal node has exactly m children. For example, consider the following trees BC D E E FG H K L M The tree on the left is a full 2-ary tree: it has 5 nodes, 3 of them D, E, and C are leaves and two of them A and B are internal nodes. In other words, we have m 2, l = 3, 2, and n 5. The tree on the right is a full 3-ary tree: it has 13 nodes, 9 leaves, and 4 internal nodes Proofs. To prove a property P of binary trees, the general recipe is . Prove P(Empty) . Assume P(t) and P(t2) hold for an arbitrary trees t and t2 and prove P(Node d ti t2) for the larger tree produced by attaching the subtrees ti and t2 to a node with data d This establishes that for every tree t, we have P(t). Sometimes the statement to prove is only valid for trees that have at least one node. In that case, the first case above is to prove P(Node d Empty Empty) for a leaf containing data d. Example Let's prove that a full binary with n nodes has 1 leaves. The statement is not true for an empty tree, so we will try to prove it for n >1. Let N(t) be the number of nodes for a tree t and L(t) be the number of leaves for a tree t. Formally we want to prove that for every non-empty tree L(t) - . Base case: t has one node, i.e., N(t) = 1, We want to prove that L(t)-N(2+1 = I. There are two constructors for trees. Since the tree is not empty, it must have been constructed using the constructor for nodes. Since we onlv have one node, it must be a leaf. . Inductive case: the tree t is constructed using Node(d, t1, t2) where t and t2 are two smaller trees with N(h) ni and N(ta)-n2. We have N(t) n + n2+ 1. By induction L(h) = n21 and (t2)-nati. The leaves of t are the leaves of both t1 and tie., L(t) = nit1 + n2+1. We need to prove: N(t) +1 2 L(t) = = nitn2+2-nit1 + n2+1 which is equal to the left hand side Example. Now that we have proved that for non-empty full binary trees L(t) -o+, we can easily write a formula for the number of internal node I(t). Indeed by definition N(t) - I(t) + L(t). So: N(t) 1 2N(t) - N(t)-1 N(t) - 1 I(t) N(t) - L(t) N(t)- 2 2 Exercises 2 Exercises . Prove that a full m-ary with n nodes has (n -1)/m internal nodes and (m -1)n + 1)/m leaves. . Prove that a full m-ary with i internal nodes has mi +1 nodes and (m -1)i 1 leaves. . Prove that a full m-ary with I leaves has (ml -1)/(m-1) nodes and (l - 1)/(m - 1) internal nodes. . Now suppose that someone starts a chain letter. Each person who receives the letter is asked to send it on to four other people. Some people do this, but others do not send any letters. Assume that everyone who forwarded the letter forwarded it to exactly four people and that all the people are distinct. Furthermore, assume that the chain letter ended after 100 people received it but did not send it out. How many people have seen the letter, including the first person? How many people sent out the letter? . Now move on to the starter files and complete the implementation of the Tree class hierarchy. . When you are done submit the solution to the exercises (as a PDF) along with your code to the autograder