Question
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
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
/** * 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
/** * 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 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 Another set of code ------------------------------------------------------------------------------------------------------------------ package comp2402a4; public class GeometricTreeNode extends BinaryTreeNode
Step 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