COMP2100/2500
Homework 6 - sorting integers

Continue filling in a new Time Recording Log and Weekly Time Use Summary each week.

Write the following program, following the enhanced PSP as described in Lecture 19 and filling in the Project Plan Summary and a Defect Recording Log. Use one of the Project Plan Summary forms that doesn't have greyed-out sections.

Write a Java program called ‘Treesort’ that uses a binary search tree to sort a list of integers.

The program must read a list of integers from the user (in much the same way as the program for Homework 2 did). As it gets each integer, it must insert it in the right place in a binary search tree.

This means: compare it to the root; if it's smaller insert it in the left subtree; if it's larger, insert it in the right subtree. The insertion into a subtree is a recursive call on the same algorithm. If the tree or subtree is empty, create a new node and put the number there. This is a recursive algorithm, similar to those in functional programming except that most of it is traversal, with an insert by changing a field in the last leaf, rather than the tree being taken apart and put back together at each node.

When the user has indicated (by entering an empty line of input) that the list is complete, the program must then print out all the numbers in the list in both ascending and descending order.

The program must use a binary search tree for sorting, not any other method. For the purposes of this homework, a binary search tree is defined as a binary tree that stores an integer in each node, and has the following properties:

• Every node in the left subtree has a value less than or equal to the value in the root node.

• Every node in the right subtree has a value strictly greater than the value in the root node.

• Both subtrees are themselves binary search trees.

Here is an example interaction with the finished program:

[comp2100@partch]$ java Treesort
Please enter data values, one per line.
> 3
> two
Invalid input, try again.
> 2
> 4
>
 
In ascending order:
2
3
4

In descending order:
4
3
2

---

Hints

You should be able to re-use quite a lot of code from Homework 3 for reading in the numbers.

I recommend that you write a class called something like BinarySearchTree for representing tree nodes, a bit like class XmlContainerElement from the project. This class will need fields: item, left and right, and methods insert(), printAscending() and printDescending. Once you have done that, the main program should be fairly easy.

Think hard about the similarities between this situation and the expression trees from Lab 2. We don't evaluate these trees, but we do traverse them to get information. You might even want to use the Visitor Pattern if you're feeling adventurous, but it's probably overkill.

This homework may be a bit longer and harder than some of the others you've had so far, so think hard about your size estimate. You will definitely need to write more than one class to solve this problem, and this immediately makes the design a bit harder. I recommend that you spend some extra time in the Design phase really understanding how to do this before you start coding. It will pay off.

(Actually, with Java you probably don't need more than one class, since the main() method can just as well live inside the class that represents your tree nodes.)

---

Extension tasks/questions (for the keen)

• What is the worst-case performance of this algorithm? What sort of input data will produce this worst-case performance?

• What is its likely performance if the input data are in random order?

• How does performance relate to the height of the tree?

• Write extra code so that the program prints out the height of the tree after each new number is added.

• Write extra code to print out the entire tree structure. Invent a suitable output format.