Anne
Dawson: CSCI201A_LAB7_FA04.htm
Last
updated: Tuesday 26th October 2004, 8:25 PT
This
document is subject to change without notice.
Please
report any errors or omissions in this document:
adawson@coquitlamcollege.com
Special instructions:
For this assignment you may work in teams of 2, or alone.
Due
Date: End of class: Week 9 Class 2: Thursday 4th November 2004
CSCI201A
Data and Program Organization (Data Structures)
Fall 2004
Lab
Assignment 7
Implementing
an efficient Binary Search Tree (BST) class.
Specification : Implement the Binary Search Tree class,
with public operations as defined in your text book, and as listed below. Exception handling should be included
where appropriate. The class should contain a constructor to construct an empty
BST. You should provide a
driver program to fully test your BST ADT.
Public operations:
insert(
x ) // insert item x
remove( x ) // remove
item x
printTree
( ) // print out the BST in sorted order
find( x
) // find item x
findMin(
x ) // find item x
findMax(
x ) // find item x
removeMin(
)// return and remove smallest
item
makeEmpty(
) // remove all items
isEmpty() // return true if empty; false
otherwise
Program
points will be based on the following marking scheme:
CSCI201A
- Lab 7 -
Implementing an efficient BST class.
Student
name(s):
|
Category |
Points |
Description |
|
Coding
Style |
10 |
The
source code should be commented and indented properly, use meaningful
variable names, use good programming practices, etc. See the book, course web
site and lectures for examples. |
|
insert(x) |
10 |
Implemented
as per specification |
|
remove(x) |
10 |
Implemented
as per specification |
|
printTree() |
10 |
Implemented
as per specification |
|
find(x) |
10 |
Implemented
as per specification |
|
findMin() |
10 |
Implemented
as per specification |
|
findMax() |
10 |
Implemented
as per specification |
|
removeMin() |
10 |
Implemented
as per specification |
|
makeEmpty() |
10 |
Implemented
as per specification |
|
isEmpty() |
10 |
Implemented
as per specification |
|
|
|
|
Source Code Format : As stated above, the source code should
follow good programming style. In addition, each file should start with a
comment block that contains the following information:
#
File: lab7.cpp or lab7.java
#
Purpose:
Implementation of an efficient BST class.
# Programmer:
[your name]
#
Partner: [your
partner's name]
#
Course:
CSCI201A
#
Date:
# Test
data: