Assignment 5

Submission

• Email your assignment to ztomasze@hawaii.edu.
• Attach the source code to your email. Send me only the source code (.java files); do not include the .class or any other files. Do not zip or otherwise bundle the .java files.

Requirements

As stated on the assignment handout, you must:

• Write a sort() method that displays the contents of a tree in decreasing order, according to the given algorithm (similar to a heapsort, though not array-based).

Suggestions

sort() doesn't need to return a String; it can just print to the screen as it goes. Note that it destroys the tree.

You should probably write a recursive helper method for the bubbling:

  private void bubble(TreeNode tree);

The traversing, on the other hand, is probably easiest to do iteratively (in a loop) within the sort method. Once you've traversed through the tree to find a leaf node, you'll also need a pointer to that leaf's parent. (You can either use another variable to keep track of a whether you went left or right from the parent; or you can just compare, with ==, to see if the leaf is the left or right child of the parent.) You need to know this when you try to remove the leaf--whether to set the parent's left or right child pointer to null.

So that you're not penalized on this assignment for poor performance on Assignment 4, I will post the code to correctly construct a BinaryTree here. I will do this 08 Nov, after the final cut-off for late submissions of Assignment 4. [BinaryTree.java and TreeNode.java].

Grading:

Out of 100 points:

10 - Compiles

85 - sort()

This means you need to the following correctly:

• Traversing to find a leaf node (25 points)
• Replacing the contents of root with the contents of that leaf (5 points)
• Removing the leaf (20 points)
• Bubbling the new root down (25 points)
• Outputting each new root (10 points)

5 - Main

You should have some kind of test of the sort method in the main method of your BinaryTree class.