Data Structure Tree

Requirements are in the TreeFunction.java file.

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 < size; i++) { result = new NodeL<>(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.class

import java.util.function.Function; @FunctionalInterface interface TriFunction { R apply(A a, B b, C c); } class WrongTreeE extends Exception { } abstract class BinTree { abstract boolean isLeaf(); abstract L getLeafData() throws WrongTreeE; abstract N getNodeData() throws WrongTreeE; abstract BinTree getLeft() throws WrongTreeE; abstract BinTree getRight() throws WrongTreeE; abstract  BinTree map(Function fnode, Function fleaf); abstract  R reduce(Function base, TriFunction f); } //----------------------------------------------------------------------- class Leaf extends BinTree { private L data; Leaf(L data) { this.data = data; } boolean isLeaf() { return true; } L getLeafData() { return data; } N getNodeData() throws WrongTreeE { throw new WrongTreeE(); } BinTree getLeft() throws WrongTreeE { throw new WrongTreeE(); } BinTree getRight() throws WrongTreeE { throw new WrongTreeE(); }  BinTree map(Function fnode, Function fleaf) { return new Leaf<>(fleaf.apply(data)); }  R reduce(Function base, TriFunction f) { return base.apply(data); } } //----------------------------------------------------------------------- class Node extends BinTree { private N data; private BinTree left, right; Node(N data, BinTree left, BinTree right) { this.data = data; this.left = left; this.right = right; } boolean isLeaf() { return false; } L getLeafData() throws WrongTreeE { throw new WrongTreeE(); } N getNodeData() { return data; } BinTree getLeft() { return left; } BinTree getRight() { return right; }  BinTree map(Function fnode, Function fleaf) { return new Node<>(fnode.apply(data), left.map(fnode,fleaf), right.map(fnode,fleaf)); }  R reduce(Function base, TriFunction f) { return f.apply(data, left.reduce(base,f), right.reduce(base,f)); } } 

Pair.java

public class Pair { private A a; private B b; Pair (A a, B b) { this.a = a; this.b = b; } A getFirst() { return a; } B getSecond() { return b; } } 

TreeFunction.java

import java.util.LinkedList; import java.util.function.BinaryOperator; /**  * Solve every problem below using ONE call to reduce. Do not use  * explicit loops, explicit recursion, or iterators.  */  public class TreeFunctions { /* Count the total number of nodes */ static  int countNodes (BinTree t) { return 0; } /* Count the leaves */ static  int countLeaves (BinTree t) { return 0; } /* Count the number of internal nodes */ static  int countInternalNodes (BinTree t) { return 0; } /* Return the maximum height of the tree */ static  int height (BinTree t) { return 0; } /* Check if a tree is balanced. A tree is balanced if every * subtree is balanced and if for every node, the heights of its * children are no more than 1 apart. To use 'reduce' here, the * result of every tree traversal will be a pair containing the * height of the tree and a boolean that states whether it is * balanced or not. */ static  boolean isBalanced (BinTree t) { return false; } /* Preorder traversal */ static List preorder (BinTree t) { return null; } /* Inorder traversal */ static List inorder (BinTree t) { return null; } /* Postorder traversal */ static List postorder (BinTree t) { return null; } /* Here the incoming tree is an expression tree (see book for * details). The big difference is that the data at each node is a * function that is applied to the results of its children. */ static int eval (BinTree,Integer> exp) { return 0; } public static void main (String[] args) { BinTree t123, t456, t7; t123 = new Node<>(1, new Leaf<>(2), new Leaf<>(3)); t456 = new Node<>(4, new Leaf<>(5), new Leaf<>(6)); t7 = new Node<>(7, t123, t456); System.out.printf("t7 has %d nodes%n", countNodes(t7)); System.out.printf("t7 has %d leaves%n", countLeaves(t7)); System.out.printf("t7 has %d internal nodes%n", countInternalNodes(t7)); System.out.printf("t7 has height %d%n", height(t7)); System.out.printf("is t7 balanced? %b%n", isBalanced(t7)); System.out.printf("preorder traversal of t7: %s%n", preorder(t7)); System.out.printf("inorder traversal of t7: %s%n", inorder(t7)); System.out.printf("postorder traversal of t7: %s%n", postorder(t7)); BinTree,Integer> exp1, exp2, exp3; exp1 = new Node<>((a,b) -> a+b, new Leaf<>(2), new Leaf<>(3)); exp2 = new Node<>((a,b) -> a-b, new Leaf<>(5), new Leaf<>(6)); exp3 = new Node<>(Math::max, exp1, exp2); System.out.printf("evaluating exp1 => %d%n", eval(exp1)); System.out.printf("evaluating exp2 => %d%n", eval(exp2)); System.out.printf("evaluating exp3 => %d%n", eval(exp3)); } /* Expected output: t7 has 7 nodes t7 has 4 leaves t7 has 3 internal nodes t7 has height 2 is t7 balanced? true preorder traversal of t7: 7,1,2,3,4,5,6,# inorder traversal of t7: 2,1,3,7,5,4,6,# postorder traversal of t7: 2,3,1,5,6,4,7,# evaluating exp1 => 5 evaluating exp2 => -1 evaluating exp3 => 5 */ }