Java Coding Part 2: use binary tree traversals to make nice(ish) drawings of binary trees. To do this, you will implement some of the functions in the GeometricTree class.

leftistDraw(): This function assigns x coordinates to nodes so that each node receives the minimum x-coordinate it can without overlapping nodes on its own level.

For whoever trying out this problem please leave a comment if you require more details on a specific class or any other issues.

Hints: For part 2, prefer to do a breadth-first traversal to traverse the levels of the tree one at a time.

Provided code is :

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

package comp2402a4;

import java.util.Random;

public class GeometricTree extends BinaryTree {

public GeometricTree() { super (new GeometricTreeNode()); } /** * Set the x and y-coordinates of each node such that it is between the * x-coordinate of its two children, no two nodes have the same * x-coordinate, and each level of the tree is drawn on separate y-coordinates. */ public void inorderDraw() { assignLevels(); // TODO: use your code here instead Random rand = new Random(); randomX(r, rand); } /** * Set the x- and y-coordinates of each node such that each node * has an x-coordinate as small as possible without overlapping * any other node at the same level and each level of the tree is * drawn on separate y-coordinates */ public void leftistDraw() { assignLevels(); // TODO: use your code here instead Random rand = new Random(); randomX(r, rand); } /** * Set the x- and y-coordinate of each node such that the smaller * of a node's two subtrees is drawn directly below the node, and the * larger is drawn directly to the right, but far enough away that * it does not intersect with the smaller subtree. */ public void balancedDraw() { assignLevels(); // TODO: use your code here instead Random rand = new Random(); randomX(r, rand); } /**This function randomly assign's x values to each node in the tree. It is for demonstration purposes only*/ 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); } /**This function sets the y values for all nodes in the tree according to their depth*/ 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); } }

Another set of code ------------------------------------------------------------------------------------------------------------------

package comp2402a4;

import java.util.LinkedList; import java.util.Queue; import java.util.Random;

public class BinaryTree> { /** * 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 > 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 > 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() > 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()

Another set of code ------------------------------------------------------------------------------------------------------------------

package comp2402a4;

/** * This class represents a node in a binary tree. This class is abstract and * should be subclassed by a concrete class. See, for example the class * SimpleBinaryTreeNode. * * @author morin * * @param * the class of the children of this node */ public class BinaryTreeNode> { public Node left; public Node right; public Node parent; }

Another set of code ------------------------------------------------------------------------------------------------------------------

package comp2402a4;

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

Actions Actions