[Homework 1] [Homework 2] [Homework 3] [Homework 4] [Homework 5] [Homework 6] [Homework 7] [Homework 8] [Homework 9] [Homework 10] [Homework 11] [Homework 12]

COMP2100
Homework 11

Due in Lab 10, Week 12.

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 program called `treesort' that uses a binary search tree to sort a list of integers.

The program shall read a list of integers from the user (in much the same way as the program for Homework 3 did). As it gets each integer, it shall 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.

When the user has indicated (by entering an empty line of input) that the list is complete, the program shall 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@karajan]$ 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 BINARY_SEARCH_TREE for representing tree nodes, a bit like class XML_CONTAINER_ELEMENT from the project. This class will need attributes: item, left and right, and commands insert (n: INTEGER), print_ascending and print_descending. 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 4. 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 adventurous.

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.

---

Extension tasks/questions (for the keen)

• What is the worst-case performance of this algorithm?

• 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.

---

Deliverables

To get your mark, you must attend your registered lab group with your lab notebook containing:

1. A completed Time Log for the past week.

2. A completed Weekly Time Use Summary for the past week.

3. A printout of your completed program.

4. A completed PSP Project Plan Summary covering the development of the program, and including a Code Review phase, defect densities, defect injection and removal rates and process yield. Calculating the A/FR is optional, but recommended.

5. A completed Defect Recording Log with details of all defects found during the development.

6. A completed Code Review checklist.

These must all be securely located in your notebook: either stuck or stapled into a standard notebook, or punched and stored in a ring binder. No loose sheets!

[Homework 1] [Homework 2] [Homework 3] [Homework 4] [Homework 5] [Homework 6] [Homework 7] [Homework 8] [Homework 9] [Homework 10] [Homework 11] [Homework 12]