Tutorial 10: Exam 2 Review


Introduction

This tutorial serves as a review to exam #2.  It is by no means exhaustive.  You need to also review all the design patterns and their implementations provided to you so far.  You also should review all the labs and all the homework assignments.   All methods must be written without checking for the type nor for the state of objects in questions.  Feel free to write helper methods to help do the job.


Study the code for the binary tree structure, BiTree, and its visitors.   In the following, assume a binary search tree contains IOrdered elements.

1.  Write a visitor called MaxTreeFinder to find and return the subtree that contains the largest element in a binary search tree host.

2. Write a visitor called MinTreeFinder to find and return the subtree that contains the smalles element in a binary search tree host.

3.  Write a visitor called OOBSTDeleter that deletes a given input element from a binary search tree host that does not check for emptiness of the subtrees.  Hint: ask one of the subtrees to delete the parent tree.

4.  Write a prefix iterator for a binary tree (study the code for the infix iterator).

5.  Bubble sort is an elementary and very slow sorting algorithm.  You can find it in many data structures textbooks.  The idea is to scan the array from bottom to top several times, swapping adjacent elements if they are out of order, so that, one at a time, the smaller elements "bubble" to the top.  Feel free to consult any textbook on bubble sort.  Here is the pseudo-code describing bubble sort on an array A[0:N] of int. 

    for (int i = 0; i < N; i++)
    {
        for (int j = N; j > i; j--)
       {
            if (A[j] < A[j-1])
            {
                 swap A[j] with A[j-1];
            }
       }
    }

Write the code to implement bubble sort to fit into Susan Merritt's sorting taxonomy.

D. X. Nguyen, April 03, 2000
dxnguyen@cs.rice.edu