Spring 1996
Assignment 8, due Tuesday April 9 at 2PM
In this assignment you will implement and use binary search trees.
You will use a binary search tree to store 3-letter airport codes, and
then your program will print out an in-order traversal of the tree.
The assignment consists of three source files (a8main.c,
a8interface.c, and a8implementation.c) that should
be compiled and linked together to make your program. In addition,
you will create two header files a8interface.h and
a8implementation.h that contain the type definitions and
function prototypes needed to support your binary search tree ADT.
Your source files are to be electronically submitted by using the submit program on csa. The code you submit
should conform with the program assignment
guidelines.
Airport Code Index
Write a8main.c, a top-level program that constructs a binary
search tree containing 3-letter airport codes. Your program should
first read an input file, building a binary search tree of the codes.
Your program should then print out the results of in-order traversal
of the tree. The result should be a listing of airport codes in
alphabetical order. Finally, your program should free the tree by
successively deleting nodes in the tree.
This program program takes one command-line argument: the input file
name. Here is an example input
file. You can assume that files conform to the 3-letter, uppercase
airport code convention.
Note: it is possible that the same airport occurs multiple times in an
input file. Your program must ensure that each possible airport code
appears only once in the binary search tree.
Binary Search Trees: Interface and Implementation Modules
Before programming, take time to define the operations that are needed
for working with the binary search tree ADT. Be sure to adhere to the
guidelines of data hiding and modularity covered in lecture and in the
text (Ch. 4). You can also use the development of the stacks and
queues ADT of Ch. 7 as a guide.
Create two header files: a8implementation.h contains
private "internal" structure type definitions and function prototypes
for your tree implementation, a8interface.h contains
function prototypes for the "public" interface.
Once basic operations have been identified, develop the interface
module in a8interface.c and the implementation module in
a8implementation.c.
Programming assignments are due before class on the
assignment due date.
Late assignments will be levied a late penalty of 10% per day. Late
assignments will only be accepted up to 4 days late.
Academic Honesty and Collaboration
It is reasonable to discuss with others possible general approaches to
problems. It is unreasonable to work together on a detailed solution,
to copy a solution, or to give away a solution. If your common
discussion can be detected by looking at the solutions, then there is
too much collaboration. Such instances of academic dishonesty will
result in a course grade of F or expulsion from Boston University.
Do not allow your work to be used by others:
- Set the permissions so that they are not readable by others.
- Do not recycle old printouts. Take them home to throw them out.
- Do not e-mail your solution to anyone.
Warning: If someone cheats by using your work, you will also be penalized
Page Created: March 11, 1996
Maintained by: Stan Sclaroff