import java.util.LinkedList; import java.util.Queue; import java.util.Random; public class BinaryTreeextends BinaryTreeNode> { /**  * Used to make a mini-factory  */  protected Node sampleNode; /**  * The root of this tree  */  public Node r; /**  * This tree's null node  */  protected Node nil; /**  * Create a new instance of this class  * @param isampleNode  */  protected BinaryTree(Node nil) { sampleNode = nil; this.nil = null; } /**  * Create a new instance of this class  * @warning child must set sampleNode before anything that  * might make calls to newNode()  */  protected BinaryTree() { } /**  * Allocate a new node for use in this tree  * @return  */  @SuppressWarnings({"unchecked"}) protected Node newNode() { try { Node u = (Node)sampleNode.getClass().newInstance(); u.parent = u.left = u.right = nil; return u; } catch (Exception e) { return null; } } public int depth(Node u) { int d = 0; while (u != r) { u = u.parent; d++; } return d; } /**  * Compute the size (number of nodes) of this tree  * @return the number of nodes in this tree  */  public int size() { return size(r); } /**  * @return the size of the subtree rooted at u  */  protected int size(Node u) { if (u == nil) return 0; return 1 + size(u.left) + size(u.right); } public int height() { return height(r); } /**  * @return the size of the subtree rooted at u  */  protected int height(Node u) { if (u == nil) return -1; return 1 + Math.max(height(u.left), height(u.right)); } /**  * @return  */  public boolean isEmpty() { return r == nil; } /**  * Make this tree into the empty tree  */  public void clear() { r = nil; } public void traverse(Node u) { if (u == nil) return; traverse(u.left); traverse(u.right); } public void traverse2() { Node u = r, prev = nil, next; while (u != nil) { if (prev == u.parent) { if (u.left != nil) next = u.left; else if (u.right != nil) next = u.right; else next = u.parent; } else if (prev == u.left) { if (u.right != nil) next = u.right; else next = u.parent; } else { next = u.parent; } prev = u; u = next; } } public int size2() { Node u = r, prev = nil, next; int n = 0; while (u != nil) { if (prev == u.parent) { n++; if (u.left != nil) next = u.left; else if (u.right != nil) next = u.right; else next = u.parent; } else if (prev == u.left) { if (u.right != nil) next = u.right; else next = u.parent; } else { next = u.parent; } prev = u; u = next; } return n; } public void bfTraverse() { Queue q = new LinkedList(); q.add(r); while (!q.isEmpty()) { Node u = q.remove(); if (u.left != nil) q.add(u.left); if (u.right != nil) q.add(u.right); } } /**  * Find the first node in an in-order traversal  * @return  */  protected Node firstNode() { Node w = r; if (w == nil) return nil; while (w.left != nil) w = w.left; return w; } /**  * Find the node that follows u in an in-order traversal  * @param w  * @return  */  protected Node nextNode(Node w) { if (w.right != nil) { w = w.right; while (w.left != nil) w = w.left; } else { while (w.parent != nil && w.parent.left != w) w = w.parent; w = w.parent; } return w; } public static extends BinaryTreeNode> void completeBinaryTree(BinaryTree t, int n) { Queue q = new LinkedList(); t.clear(); if (n == 0) return; t.r = t.newNode(); q.add(t.r); while (--n > 0) { Node u = q.remove(); u.left = t.newNode(); u.left.parent = u; q.add(u.left); if (--n > 0) { u.right = t.newNode(); u.right.parent = u; q.add(u.right); } } } /**  * Create a new full binary tree whose expected number of nodes is n  * @param   * @param t  * @param n  */  public static extends BinaryTreeNode> void galtonWatsonFullTree(BinaryTree t, int n) { Random r = new Random(); Queue q = new LinkedList(); t.clear(); t.r = t.newNode(); q.add(t.r); double p = ((double)0.5 - ((double)1)/(n+n)); while (!q.isEmpty()) { Node u = q.remove(); if (r.nextDouble() left = t.newNode(); u.left.parent = u; q.add(u.left); u.right = t.newNode(); u.right.parent = u; q.add(u.right); } } } static extends BinaryTreeNode> void galtonWatsonTree(BinaryTree t, int n) { Random r = new Random(); Queue q = new LinkedList(); t.clear(); t.r = t.newNode(); q.add(t.r); double p = ((double)0.5 - ((double)1)/(n+n)); while (!q.isEmpty()) { Node u = q.remove(); if (r.nextDouble() left = t.newNode(); u.left.parent = u; q.add(u.left); } if (r.nextDouble() right = t.newNode(); u.right.parent = u; q.add(u.right); } } } } 

----------------------------------------------------------------------------------------------------

public class BinaryTreeNodeextends BinaryTreeNode> { public Node left; public Node right; public Node parent; } 

-------------------------------------------------------------------------------------------------------

public class GeometricTreeNode extends BinaryTreeNode { public Point2D position; public GeometricTreeNode() { position = new Point2D(); } public String toString() { return position.toString(); } } 

--------------------------------------------------------------------------------------------

public class Point2D { public int x, y; public String toString() { return "(" + x + "," + y + ")"; } } 

--------------------------------------------------------------------------------------------

PLEASE MODIFY THIS CLASS  import java.util.Random; public class GeometricTree extends BinaryTree { public GeometricTree() { super (new GeometricTreeNode()); } public void inorderDraw() { assignLevels();  Random rand = new Random(); randomX(r, rand); } protected void randomX(GeometricTreeNode u, Random r) { if (u == null) return; u.position.x = r.nextInt(60); randomX(u.left, r); randomX(u.right, r); } /**  * Draw each node so that it's x-coordinate is as small  * as possible without intersecting any other node at the same level  * the same as its parent's  */  public void leftistDraw() { assignLevels(); Random rand = new Random(); randomX(r, rand); } public void balancedDraw() { assignLevels(); //ADD CODE HERE  /*Random rand = new Random(); randomX(r, rand);*/ } protected void assignLevels() { assignLevels(r, 0); } protected void assignLevels(GeometricTreeNode u, int i) { if (u == null) return; u.position.y = i; assignLevels(u.left, i+1); assignLevels(u.right, i+1); } public static void main(String[] args) { GeometricTree t = new GeometricTree(); galtonWatsonTree(t, 100); System.out.println(t); t.inorderDraw(); System.out.println(t); } } 

Part 3, you want to compute the sizes of all subtrees in advance (using a post-order traversal) and store them in a HashMap. Then do a second traversal to compute the x and y coordinates. Requirement:Your implementation here should be fast and non-recursive. The test program will test your implementations of these functions on very large (e.g., 100k node) trees. All your implementations should run in linear time and should be able to label a 100k node tree in a tenth of a second or so. Your implementation should work even if the tree is extremely unbalanced Part 3, you want to compute the sizes of all subtrees in advance (using a post-order traversal) and store them in a HashMap. Then do a second traversal to compute the x and y coordinates. Requirement:Your implementation here should be fast and non-recursive. The test program will test your implementations of these functions on very large (e.g., 100k node) trees. All your implementations should run in linear time and should be able to label a 100k node tree in a tenth of a second or so. Your implementation should work even if the tree is extremely unbalanced