NEED WITHIN THE HOUR PLEASE

Write a stutter method for IntTree (NOT SearchTree):

(A. is just the public access to call part B):

A. partialStutter(); a public non-recursive method that changes this tree to add stutter nodes (one Node with same data) on the right when possible, otherwise add a stutter node on the left, but if both left and right are not null then the node cannot be stuttered (thus called partial stutter). The null node is not changed. See example with tree27 below.

B. partialStutter(IntTreeNode root); a private recursive method helper, returns an IntTreeNode, that does the tree traversal and modification for public partialStutter();

You can either use your existing IntTree.java from your work on the exercises TODO. Or you can start from scratch with a fresh copy of IntTree.java as posted for the TODO chapter 17. I will also use IntTreeNode.java with this quiz.

Further explanation: stutter() from our text is in almost every chapter, so let's do it again. Each node will have a copy added as a right child, or not at all, thus we don't exactly double the size. Parts A and B are really one problem if you've followed along how these tree exercises go, the client calls a public method (A) that calls a recursive helper (B).

INTTREE.JAVA CODE:

public class IntTree { private IntTreeNode overallRoot;

// pre : max > 0 // post: constructs a sequential tree with given number of // nodes public IntTree(int max) { if (max <= 0) { throw new IllegalArgumentException("max: " + max); } overallRoot = buildTree(1, max); } public IntTree() { overallRoot = null; } // constructor added so we can build page 1029 reference trees public IntTree(IntTreeNode given) { overallRoot = given; }

// ADD METHODS here for exercises:

// post: returns a sequential tree with n as its root unless // n is greater than max, in which case it returns an empty tree private IntTreeNode buildTree(int n, int max) { if (n > max) { return null; } else { return new IntTreeNode(n, buildTree(2 * n, max), buildTree(2 * n + 1, max)); } }

// post: prints the tree contents using a preorder traversal public void printPreorder() { System.out.print("preorder:"); printPreorder(overallRoot); System.out.println(); }

// post: prints the tree contents using a preorder traversal // post: prints in preorder the tree with given root private void printPreorder(IntTreeNode root) { if (root != null) { System.out.print(" " + root.data); printPreorder(root.left); printPreorder(root.right); } }

// post: prints the tree contents using a inorder traversal public void printInorder() { System.out.print("inorder:"); printInorder(overallRoot); System.out.println(); }

// post: prints in inorder the tree with given root private void printInorder(IntTreeNode root) { if (root != null) { printInorder(root.left); System.out.print(" " + root.data); printInorder(root.right); } }

// post: prints the tree contents using a postorder traversal public void printPostorder() { System.out.print("postorder:"); printPostorder(overallRoot); System.out.println(); }

// post: prints in postorder the tree with given root private void printPostorder(IntTreeNode root) { if (root != null) { printPostorder(root.left); printPostorder(root.right); System.out.print(" " + root.data); } }

// post: prints the tree contents, 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 printSideways() { printSideways(overallRoot, 0); }

// post: prints in reversed inorder the tree with given // root, indenting each line to the given level private void printSideways(IntTreeNode root, int level) { if (root != null) { printSideways(root.right, level + 1); for (int i = 0; i < level; i++) { System.out.print(" "); } System.out.println(root.data); printSideways(root.left, level + 1); } } // toString() added by W.P. Iverson for simple console testing // since String is immutable, I've used StringBuilder public String toString() { StringBuilder s = new StringBuilder(); toString(overallRoot, 0, s); return s.toString(); } // similar reverse in order traversal of tree as print sideways private void toString(IntTreeNode root, int level, StringBuilder s) { if (root != null) { toString(root.right, level + 1, s); String temp = new String(); // different for each node for (int i = 0; i < level; i++) { temp += " "; } s.append(temp + root.data + " "); // uses same String in recursions toString(root.left, level + 1, s); } } }