nstructions

Using the attached files, TreeAssignment.java and IntTree.java Add to the methods in IntTree so that the sumNodes methods returns the sum of all the integers in the tree. countLeftNodes should count up all the left children in the tree. Provided in IntTree.java is an example to help you called countEvenBranches which counts all the branches (nodes with children) with even values, but not leaves (nodes with no children) with even values. Both methods return an integer. The tree generated is random so each run will be slightly different. Turn in both files in your submission. public class TreeAssignment { // DO NOT CHANGE LINES IN MAIN- YOU MAY ADD AT BOTTOM BUT NOT REMOVE ANY LINES public static void main(String[] args) { // create int tree with 10 random elements // you may make this smaller for testing IntTree theTree = new IntTree(3); // print the tree theTree.printStructure(); // call already developed routine to count even branches - this // counts branches with even nodes, not even leaf nodes int evenCount = theTree.countEvenBranches(); System.out.println("There are " + evenCount + " even branches"); // call user developed routine to count left Nodes int leftNodes = theTree.countLeftNodes(); System.out.println("The number of left nodes is " + leftNodes); // call second user developmed routine to sum the values of all the integers in the tree int totalSum = theTree.sumNodes(); System.out.println("The total sum is " + totalSum); } } -------------------------------------------------

// Stuart Reges / Marty Stepp // Simple class that includes methods to construct a random tree of ints, to // print the structure, and to print the data using a preorder, inorder or // postorder traversal.

public class IntTree { private IntTreeNode overallRoot; public IntTree() { this((IntTreeNode) null); }

// pre : height >= 0 // post: constructs a perfect binary tree of given height with random // data values between 0 and 99 inclusive public IntTree(IntTreeNode overallRoot) { this(overallRoot, true); }

// post: constructs a binary tree using the given root; // if copy is true, makes a deep copy of all of its nodes public IntTree(IntTreeNode overallRoot, boolean copy) { if (copy) { this.overallRoot = deepCopy(overallRoot); } else { // just use this one this.overallRoot = overallRoot; } } private IntTreeNode deepCopy(IntTreeNode root) { if (root == null) { return null; } else { return new IntTreeNode(root.data, deepCopy(root.left), deepCopy(root.right)); } }

// pre : height >= 0 // post: constructs a perfect binary tree of given height with random // data values between 0 and 99 inclusive public IntTree(int height) { if (height < 0) { throw new IllegalArgumentException(); } overallRoot = randomTree(height); }

private IntTreeNode randomTree(int h) { return randomTree(h, true); } // pre : height >= 0 // post: constructs and returns a reference to a perfect binary tree // of height h with random data values between 0 and 99 inclusive private IntTreeNode randomTree(int h, boolean perfect) { if (h == 0) { return null; } else { int n = (int) (Math.random() * 100); IntTreeNode node = new IntTreeNode(n); if (perfect || Math.random() >= 0.75) { node.left = randomTree(h - 1); } if (perfect || Math.random() >= 0.75) { node.right = randomTree(h - 1); } return node; } } public IntTree(String s) { overallRoot = fromString(new StringBuilder(s.toLowerCase().trim())); }

public boolean equals(Object o) { IntTreeNode.clearCycleData(); if (o instanceof IntTree) { IntTree other = (IntTree) o; return this.overallRoot == other.overallRoot || equals(this.overallRoot, other.overallRoot); } else { return false; } }

private boolean equals(IntTreeNode root1, IntTreeNode root2) { if (root1 == null || root2 == null) { return root1 == root2; } else { return root1.data == root2.data && (root1.left == root2.left || equals(root1.__gotoLeft(), root2.__gotoLeft())) && (root1.right == root2.right || equals(root1.__gotoRight(), root2.__gotoRight())); } }

// post: prints the data fields of the tree using a preorder traversal public void printPreOrder() { IntTreeNode.clearCycleData(); System.out.print("preorder:"); printPreOrder(overallRoot); System.out.println(); }

// post: prints in preorder the data fields of the tree with given root private void printPreOrder(IntTreeNode root) { if (root != null) { System.out.print(" " + root.data); printPreOrder(root.__gotoLeft()); printPreOrder(root.__gotoRight()); } }

// post: prints the data fields of the tree using an inorder traversal public void printInOrder() { IntTreeNode.clearCycleData(); System.out.print("inorder:"); printInOrder(overallRoot); System.out.println(); }

// post: prints in inorder the data fields of the tree with given root private void printInOrder(IntTreeNode root) { if (root != null) { printInOrder(root.__gotoLeft()); System.out.print(" " + root.data); printInOrder(root.__gotoRight()); } }

// post: prints the data fields of the tree using a postorder traversal public void printPostOrder() { IntTreeNode.clearCycleData(); System.out.print("postorder:"); printPostOrder(overallRoot); System.out.println(); }

// post: prints in postorder the data fields of the tree with given root private void printPostOrder(IntTreeNode root) { if (root != null) { printPostOrder(root.__gotoLeft()); printPostOrder(root.__gotoRight()); System.out.print(" " + root.data); } }

// post: prints the data fields of the tree, one per line, following // an inorder traversal and using indentation to indicate node depth; // prints right to left so that it looks correct when the output is // rotated. public void printStructure() { IntTreeNode.clearCycleData(); printStructure(overallRoot, 0); }

// post: prints in preorder the data fields of the given tree indenting // each line to the given level private void printStructure(IntTreeNode root, int level) { if (root != null) { printStructure(root.__gotoRight(), level + 1); for (int i = 0; i < level; i++) { System.out.print(" "); } System.out.println(root.data); printStructure(root.__gotoLeft(), level + 1); } } public IntTreeNode getRoot() { return overallRoot; } public void setRoot(IntTreeNode root) { overallRoot = root; } public String toString() { int size = __getSize(); int height = __getHeight(); int widest = __getWidest() + 1; IntTreeNode.clearCycleData(20); String result = toString(overallRoot, 0, 0, size, height, widest); if (overallRoot == null) { result = "overallRoot null"; } else { String firstLine = ""; int nodesLeft = __getSize(overallRoot.left); if (overallRoot.left != null && (overallRoot.cycle() || overallRoot.left.cycle())) { // nodesLeft = 0; } int spaces = (nodesLeft * widest) - Math.max(0, "overallRoot".length() - widest + 1) / 2; for (int i = 0; i < spaces; i++) { firstLine += " "; } firstLine += "overallRoot "; int len = result.length(); while (len < firstLine.length()) { result = " " + result; len += 2; } result = firstLine + result; } return result; } private String toString(IntTreeNode root, int sizeAboveLeft, int level, int size, int height, int width) { // System.out.println("toString(root, " + sizeAboveLeft + ", " + level + ", " + size + ", " + height + ", " + width + ")"); if (root == null) { return ""; } else { String result = ""; int sizeBelowLeft = __getSize(root.left); if (root.cycle()) { // sizeBelowLeft = 0; } int sizeLeft = sizeAboveLeft + sizeBelowLeft;

// create line for this element // (must potentially put leading __ marks for left/right pointers) String thisElementLine = ""; String nextLine = "";

if (root.left == null) { // indent this node for (int i = 0; i < width * sizeAboveLeft; i++) { thisElementLine += " "; if (root.right != null) { nextLine += " "; } } } else { // indent this node, but insert / and _____ for left pointer int widthOfLeft = root.left.toString().length(); int dWidthLeft = width - widthOfLeft; int betweenLeft = __getSizeBetweenLeft(root); if (root.cycle()) { // betweenLeft = 0; } for (int i = 0; i < width * (sizeLeft - betweenLeft) - dWidthLeft; i++) { thisElementLine += " "; nextLine += " "; } thisElementLine += " "; nextLine += "/"; for (int i = 0; i < width * betweenLeft - 1 + dWidthLeft; i++) { thisElementLine += "_"; if (root.right != null) { nextLine += " "; } } }

thisElementLine += root; if (root.right != null) { // insert _____ and \ for right pointer for (int i = 0; i < root.toString().length(); i++) { nextLine += " "; } for (int i = 0; i < width - root.toString().length() - 1; i++) { thisElementLine += "_"; nextLine += " "; } int betweenRight = root.cycle() ? 0 : __getSizeBetweenRight(root); for (int i = 0; i < width * betweenRight; i++) { thisElementLine += "_"; nextLine += " "; } nextLine += "\\"; } if (root.left == null && root.right == null) { result += thisElementLine; } else { thisElementLine += " "; nextLine += " ";

// append all left elements String leftLines = root.cycle() ? "" : toString(root.__gotoLeft(), sizeAboveLeft, level + 1, size, height, width);

// append all right elements String rightLines = root.cycle() ? "" : toString(root.__gotoRight(), sizeLeft + 1, level + 1, size, height, width);

result += thisElementLine + nextLine + mergeLines(leftLines, rightLines); }

return result; } } private String mergeLines(String left, String right) { String[] leftLines = left.split(" "); String[] rightLines = right.split(" "); String[] resultLines = new String[Math.max(leftLines.length, rightLines.length)]; for (int i = 0; i < resultLines.length; i++) { if (i >= rightLines.length) { resultLines[i] = leftLines[i]; } else if (i >= leftLines.length) { resultLines[i] = rightLines[i]; } else { resultLines[i] = leftLines[i]; if (rightLines[i].length() > leftLines[i].length()) { resultLines[i] += rightLines[i].substring(leftLines[i].length()); } } } String result = ""; for (String line : resultLines) { if (result.length() > 0) { result += " "; } result += line; } return result; } private int __getSizeBetweenLeft(IntTreeNode root) { if (root == null || root.left == null) { return 0; } else { return __getSize(root.__gotoLeft().__gotoRight()); } } private int __getSizeBetweenRight(IntTreeNode root) { if (root == null || root.right == null) { return 0; } else { return __getSize(root.__gotoRight().__gotoLeft()); } } private int __getHeight() { IntTreeNode.clearCycleData(); return __getHeight(overallRoot); } private int __getHeight(IntTreeNode root) { if (root == null) { return 0; } else { int leftHeight = 0; IntTreeNode left = root.__gotoLeft(); if (left != null && !left.cycle()) { leftHeight = __getHeight(left); } int rightHeight = 0; IntTreeNode right = root.__gotoRight(); if (right != null && !right.cycle()) { rightHeight = __getHeight(right); } return (root.cycle() ? 0 : 1) + Math.max(leftHeight, rightHeight); } } private int __getSize() { IntTreeNode.clearCycleData(); return __getSize(overallRoot); } private int __getSize(IntTreeNode root) { if (root == null) { return 0; } else { int leftSize = 0; IntTreeNode left = root.__gotoLeft(); if (left != null && !left.cycle()) { leftSize = __getSize(left); } int rightSize = 0; IntTreeNode right = root.__gotoRight(); if (right != null && !right.cycle()) { rightSize = __getSize(right); } return (root.cycle() ? 0 : 1) + leftSize + rightSize; } } private int __getWidest() { IntTreeNode.clearCycleData(); return __getWidest(overallRoot); }