Figure 1: Positions in a binary tree.
University of Toronto
CSC148H: Introduction to Computer Science
Summer 1997
Assignment 4: Make like a tree and ...
Due: Thursday, July 17, 6pm.
You are to write a recursive function that counts and returns the number of leaves in a binary tree. We will supply a binary tree class and a driver program, so that the only thing you'll have to do is fill in a function. Like assignment 1, this assignment will be automatically evaluated.
Download the BinaryTree class and the driver from the course web page. The Init and PrintIt procedures of the class are self-explanatory. InsertInPlace was written in order to make testing your function easier. Its first parameter is a number that represents the position in the tree where you want to insert the key, and the second is the key (a string). Figure 1 shows how the positions of a tree are labelled from top to bottom, and from left to right. For InsertInPlace to work properly, you must have inserted a node's parent before inserting the node. So, by using InsertInPlace, the driver can build a binary tree with any structure you desire.
Figure 1: Positions in a binary tree.
Fill in the CountLeaves function. It takes no parameters, but it should return the number of leaves in the tree. You must solve the problem recursively. To do this, you'll have to write a separate function that actually does the work, and use the CountLeaves function to just set up the recursion. For a model, look at how PrintIt calls recPrintIt. Note: the whole recursive function should be about 10 lines of code.
If you are still confused about recursion, follow the advice on slides 328-331 of the lecture notes.
The driver expects a series of place/key pairs as input, followed by -1 to end the series. Figure 2 shows an example of some input and the resulting output of the driver.
Figure 2: Example of input and output of the driver program.
IMPORTANT: Since your function will be automatically evaluated by a computer program, its output must match, character for character, what we expect. Therefore, do not use or add any output statements of your own, and do not alter the BinaryTree class, except to add your function(s). If your output is different in any way, it will be considered wrong.
Submit your assignment electronically. All we need is your BinaryTree class. Make sure that it's named tree.tu and submit it using the ``Hand in (submit)'' command, found under the ``File Utilities'' icon on the CDF-PCs. If you submit more that once, then the most recent submission will replace any previous ones. If your file is not named tree.tu, the automatic tester won't find it, and you'll receive a mark of zero. If your program does not compile, you will also receive a mark of zero. So, make sure the version that you submit works.