Using the attached files, TreeAssignment.java and IntTree.java Add to the method
ID: 3732680 • Letter: U
Question
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);
}
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);
}
}
-------------------------------------------------
Explanation / Answer
private int sumNodes(IntTreeNode root) {
if (root == null)
return 0;
return (root.data + sumNodes(root.__gotoLeft()) + sumNodes(root.__gotoRight()));
}
private int countLeftNodes(IntTreeNode node)
{
int cleft = 0;
if (node.__gotoLeft() != null)
{
cleft += 1 + countLeftNodes(node.__gotoLeft());
}
if(node.__gotoRight() != null)
{
cleft += countLeftNodes(node.__gotoRight());
}
return cleft;
}
private int countEvenBranches(IntTreeNode root) {
if ((root == null) || (root.__gotoLeft() == null) || (root.__gotoRight() == null)) {
return 0;
} else if (root.data % 2 == 1 ){
return countEvenBranches(root.__gotoLeft) + countEvenBranches(root.__gotoRight);
} else {
return 1 + countEvenBranches(root.__gotoLeft) + countEvenBranches(root.__gotoRight);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.