Lab

Binary Search Tree

Prelab Task:

    1. Review what we learned about binary search tree.

    2. Finish the implementation of the class integer in "int.h"

Lab Task:

In the lab, we will use binary search tree data structure to store data and search a value. The data we will use in this lab is integer object you created in the prelab.

1.  Read and understand the header file d_stree.h

2.  Write a main program that generates 10,000 random integers in the range from 0 to 6. For each value, construct an integer object, and search the tree. If the value is in the tree, increment its count, otherwise, insert the value, with a count of 1. In your program, you need first to declare a binary search tree integerTree using d_stree.h, then search the tree, finally output its nodes in order and picture the tree by calling displayTree().

2.1 Copy the following files: d_except.h,  d_random.h,  d_stiter.h,  d_stree.h to your working directory for this lab and you may need them for your lab. You may need to include <utility> header file too. In addtion, don't include "d_stiter.h" in the main file (since d_stree.h file already contains d_stiter.h" file). You may also use C++ STL random generator that you learned in COSC 120 (if you have problem with d_random.h).

2.2 Name the program for the lab  as lab_05.cpp and put your int.h into your working directory for this lab too.

2.3 Compare your output for program lab_04.cpp with the sample output.

What to Turn In

Hand in the source codes for int.h and lab_05.cpp and sample outputs to the instructor.