Lab 14: Binary Search Trees

Lab Objectives

·  Use an iterator to traverse a binary search tree

·  Use an iterator to update a binary search tree

Lab References

·  Chapter 24: Trees and tree traversals in general

·  Chapter 25: Binary tree implementations and the BinaryNode and BinaryTree classes

·  Chapter 26: Binary search trees and the BinarySearchTree class

Problem Description

An iterator is used to visit each node in a tree. Different iterators are used to traverse the tree in different ways. This lab will use the preorder and inorder iterators to visit the nodes. A preorder traversal first visits the root node, then visits all of the nodes in the left subtree, and finally visits all the nodes in the right subtree. In contrast, an inorder traversal first visits all the nodes in the left subtree, then visits the root node, and finally visits all the nodes in the right subtree.

Iterators can also be used to gain access to the nodes for updating.

Files Required

·  BinaryNode.java

·  BinaryNodeInterface.java

·  BinarySearchTree.java

·  BinaryTree.java

·  BinaryTreeInterface.java

·  City.java

·  Item.java

·  LinkedQueue.java

·  LinkedStack.java

·  MyProgram.java

·  QueueInterface.java

·  SearchTreeInterface.java

·  SavitchIn.java

·  StackInterface.java

·  TreeInterface.java

·  TreeIteratorInterface.java

Lab Exercise

  1. Examine the file MyProgram.java. This program creates a binary search tree of cities and then performs an inorder traversal of the tree. Run the program.
  2. Add statements to the program that perform a preorder traversal on the binary search tree of cities. Run the program.
  3. On paper draw the binary search tree that the program creates.
  4. Draw another binary search tree that contains the same cities, but is of minimal height.
  5. In the MyProgram.java, create a second binary search tree that matches the tree that you drew in the previous step. Display the inorder and preorder traversals. How do these traversals compare with those you obtained for the first binary search tree?
  6. Notice the update method in MyProgram; it increases a given city's population by 10%. Using this method, revise the main method so that it increases the population of each city in the binary search tree. Do this in such a way that you do not change the shape of the tree.
  7. Next delete from the tree all cities with a population under one million. To do this, use an iterator to visit each city in the tree and examine the city's population. If the population is under 1 million, delete the node that contains the city. Use the remove method for the binary search tree. The remove method for the iterator throws an exception.

Questions

  1. Describe why your revision of the data (increasing the population) in the tree did not change the shape of the tree.
  2. Could you correctly fix a typo in a city name using a technique similar to the one used to increase the population.
  3. How would a client of the class BinarySearchTree update a city's population without using an iterator?
  4. Would the method that you described in question 3 change the shape of the tree. Why? Does it matter?