15-121 FALL 2018 (Reid-Miller)

Lab 10


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

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

  2. Write a method countInternal in the BinaryTree class that returns the number of internal nodes (including the root) in the binary tree. Your method should have the following signature:

    public int countInternal()

    Note that this method should not be recursive. It should call another private method that is recursive to do the computation. (WHY?) Run the associated tester to check your solution.

  3. Write a method height in the BinaryTree class that returns the height of a binary tree. Recall the height of a tree is the number of links in the longest path from the root to a leaf. Because the height of a leaf node is 0, it is convenient to define the height of an empty tree to be -1. Why? 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.

  4. [HARDER] Write a method isPerfect for the BinaryTree class that returns true if the binary tree is perfect or false otherwise. Recall a binary tree is perfect if all the leaves are at the same level and every non-leaf has exactly two children. An empty tree is considered perfect. (You'll need a recursive helper method here too.)

    HINT: The solution is recursive and is similar to 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 Autolab. (If you worked together, you only have to submit one program.)

FUTURE WORK: FUN STUFF FOR LATER