15-121 SPRING 2010 [CORTINA]

LAB 8

Binary-tree visualization of the Yahoo search engine bot crawling an experimental website.
From www.computergraphica.com

In this lab, you will implement several recursive methods using binary trees.

EXERCISES

Download the project Lab8.zip. It contains the binary tree class discussed in lecture. Although this code is given to you, along with the testers for your exercises, you should read through this code carefully after lab to make sure you can write this code yourself.

Look at any of the testers and examine the definitions for the seven binary trees. Draw each binary tree on a piece of paper before proceeding on. (All three testers use the same seven binary trees.) Check with your neighbors to make sure you draw the binary trees correctly.
Write a method count in the BinaryTree class that returns the total number of nodes stored in the binary tree. Your method should have the following signature:
public int count()
Note that this method should not be recursive, but it should call another private method that is recursive to do the computation. (Why can't the public method be recursive?) Run the associated tester to check your solution.
Write a method height in the BinaryTree class that returns the height of a binary tree. The height of an empty tree is 0. If the tree is not empty, the height of the tree is the number of nodes along the path from the root to the deepest leaf. Your method should have the following signature:
public int height()
Note that this method should not be recursive. It should call another private method that is recursive to do the computation. Run the associated tester class to check your solution.
[HARDER] Write a method isFull for the BinaryTree class that returns true if the binary tree is full or false otherwise. An empty tree is considered full. (You'll need a recursive helper method here too.)

HINT: The solution is recursive and depends on your height method from the previous exercise.

HANDIN

If you worked with another student, put both of your names in a comment at the beginning of your program. At the end of lab, create a zip file of your program and submit it to the handin server http://handin.intro.cs.cmu.edu/v1. (If you worked together, you only have to submit one program.)

FUTURE WORK: FUN STUFF FOR LATER

Write an application that takes a postfix expression (RPN) and builds an expression tree based on the postfix expression.
Write an application that encodes a message into Morse Code. (See p. 460 in your textbook for details on how to do this.
Rewrite the toString method so that it returns a string that contains the data of the tree shown horizontally, level by level, rather than vertically.