An Introduction to Trees in Java

Goals

This lab considers a binary search tree as a specific type of tree and provides practice with how such a tree structure might be implemented in Java.

Background

1. Review the readings for this lab regarding the basic defintions of general trees and binary search trees.

2. Which of the following trees is(are) a binary search tree(s)?

Implementing Binary Search Trees in Java

The implementation of a binary search tree in Java follows a similar approach to our implementation of lists.

• Each data element in a tree is considered an object of a TreeNode class. Program ~walker/java/examples/trees/TreeNode.java shows a typical declaration for such a node class.

• A BSTree class combines the nodes into an overall structure. As with the school directory example in the reading on generalization, we consider the following basic operations:

  • construct a tree,
  • add an entry,
  • retrieve an entry, given the name,
  • update an entry,
  • print all entries (alphabetically by name), and
  • remove an entry.

  Program ~walker/java/examples/trees/BSTree.java implements a binary search tree, including several methods already identified. This program also contains the same testing sequence used for the SchoolDirectory program involving lists.

This lab's readings discuss the approaches and implementations for each of these Java classes.

3. Copy ~walker/java/examples/trees/TreeNode.java and ~walker/java/examples/trees/BSTree.java to your account. Compile and run the programs to verify they produce the same results as the SchoolDirectory program described in the reading on generalization.

4. What can you say about the order of the entries printed by the print procedure? Explain why this sequence is obtained.

The discussion of insertion into a binary search tree in the reading for this lab described the insertion of the number 153 into the following tree (which repeats the tree given above).

5. Suppose a similar insert method was used to build the tree in the above example (with numbers 23, 37, 48, 96, 123, 185, 200, 285, and 309 rather than names and entries).

   1. What data do you think would have to be inserted first into the null tree?
   2. What item or items might have been inserted next?
   3. What flexibility might there be in the order of entering data to get the above tree, and what restrictions might apply?

   Explain your answers.

6. Given the order of insertions in the main method of ~walker/java/examples/trees/BSTree.java, draw a picture of the binary search tree that is produced by that program.

7. Add an update method to the BSTree class, analogous to the corresponding method for the SchoolDirectory program from the lab on generalization.

   Note: As with the similar problem for the SchoolDirectory, the body of this update method can be just two lines long!

Additional Practice

8. Write an iterative version of the recursive lookup method.

9. Use ideas from print to write a printLeaves method, which prints just the leaves within a tree. Here, one can still traverse the full tree -- but printing should occur only if a node has only null left and right subtrees.

10. Ideas from print also can be used to count the number of (non null) nodes in a tree. Use this approach to write a countNodes method.

Extra Credit:

11. The height of a tree is the maximum number of levels of nodes within the tree; by convention, the height of a tree with only one node is 0. Thus, the binary search tree shown between parts 4 and 5 above (with root 123) has height 3. Add to the BSTree class a method height which computes the height of a tree.

Work to be turned in:

• Discussion for parts 2, 4 and 5.
• Picture of the tree for part 6.
• Code, with test runs, for parts 7, 8, 9, and 10.
  (All completed operations may be included in a single program listing.)
• (Optional) Code, with test runs, for part 11.

This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/153.sp05/labs/lab-intro-trees.shtml

created April 18, 2000 last revised March 24, 2005
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.