Exercise 6

Binary Search Trees (BST)

Due Date - April 28, 2012 @ 2:00pm

Introduction

Trees are a very used data structure. A tree is a structure composed of a root, many branches starting and at the hightest depth of each branch reaches the leaves.  Applying constrains to a Tree structure generates a specialized version of a Tree structure, and this results to be very useful. For example Binary Trees are Trees constrained to have at most one branch connecting to a parent, one branch connecting its left child and one branch connecting its right child. Binary Trees are very useful because they are a great tool when performing frequent operations such as sorting. There is specializations of binary trees as well. For example a Binary Heap is created using a Binary Tree structure. A Binary Heap is useful when implementing  what is called as a Priority Queue. Other implementations of Trees are Splay Tree, Red black tree, B-Tree among many others.

In this exercise you will be implementing traversal methods for a specialized Binary Tree called Binary Search Tree (BST). The traversal of a data structure is a way to visit all the nodes inserted in the structure.

Links about BSTs:

Animation of BST traversals

Video explaining BST structures

Binary Search Tree (from Wikipedia)

Assignment

      Write a C program that performs insertion of elements in a  BST, then print preorder, inorder and postorder traversal. A file will be given with the elements that need to be inserted.

Output Code

    You can download the code for the expected output here.  The output code contains the function that handle all the errors that you have to handle.

PrintError - Prints the appropriate error messages if you have problems opening a file, if there is the wrong number of command-line inputs, or failure of memory allocation.

Specifications

1. You should print an error message and exit the program with a value of EXIT_FAILURE if the user does not give enough command line arguments.  The expected output is in the output code (error code 1).
2. You should print an error message and exit the program with a value of EXIT_FAILURE if the user gives an invalid file.  The expected output is in the output code (error code 2).
3. You should print an error message and exit the program with a value of EXIT_FAILURE if the dynamic memory is not allocated properly.  The expected output is in the output code (error code 3).
4. The name of file containing the set will be given as a the first command-line argument.
5. The case of the traversal (1. preorder 2. inorder 3. postorder) will be given as the second command-line argument.
6. You can assume the values given in the file to be integers, one for each line in the input text file. (Hint: use strtol() to convert from strings to integers.)
7. Your insertion in the Binary Tree must be using the constraints of a BST . (If a node is a right child, its value should be more than its parent. If a node is a left child, then its value should be less than its parent ).
8. There is no maximum number of values in a set.
9. You will need to dynamically allocate memory to store the set.
10. Only one instance of a value will be in a set. (Each value in the set is unique).
11. The largest number possible in the set is 1000000

Warning

You are not allowed to use anything like the following:

    int count = 0;
    ... /* find the number of elements */
    int array[count]; 

You have to use malloc and free.

Compile and Execute

You will need to create a Makefile to compile your code.  You can find an introduction on Makefiles here.  You should use "gcc -Wall" instead of "gcc".  This will turn on warning messages.  Treat warning messages seriously because warnings are very likely errors.

Warning messages are often indications of errors. For this assignment, you lose 0.1 point for each warning message. The command will generate an executable file called "ex6."

To execute this program, type

./ex6 <filename> <print>

The argument (argv[1]) is the file containing the set.

The argument (argv[2]) is the type of traversal that we expect.

If argv[2]=1 Your program should print the value of each node while doing a preorder traversal.

If argv[2]=2 Your program should print the value of each node while doing an inorder traversal.

             If argv[2]=3 Your program should print the value of each node while doing a postorder traversal.

Testcases

You can download some test cases from here. In the meanwhile, use the example given at the end of this site.

Submission Procedure

   Create a zip file contain the folowing files

• At least 1 .c and 1 .h file
• Makefile - The makefile should produced the executable "ex6".
• Readme - Explain briefly the code for your solution to this exercise.

   and then submit to the course grading website. 

You need to provide a user name and a password through Blackboard before submission.  The user name and the password are different from your Purdue career account.

.h Files

A .h file, short for header file,  typically contains the following

• All the the C library files that your program will need (i.e. stdio.h, stdlib.h, etc.)
• All constants you will need.  Constants can be defined using the #define command.  An example would be  "#define MAXLEN 102".
• All function headers  for the function in your program. 
• All Structures used.

Once completed, your .h file should be included in your .c file.  This is done by typing the following: #include "filename.h"

Memory Management

Memory management (allocation and release) is an important part of ECE 264. You have to allocate enough memory to make your program work. You have to allocate and release memory as needed. You are not allowed to allocate a large piece of memory regardless of the input size. We will restrict stack size to prevent that. You will receve heavy penalty (50%) if your program does not release all memory (i.e. memory leak). We will use valgrind to check for memory leaks.

If you use Eclipse, you can set up valgrind following this link.

Grading

The maximum score for this exercise is 2.0 points.

Example

For the set is given in the following order:

{5, 3, 7, 1, 6, 8}

If argv[2]=1 Your program should output:

5 3 1 7 6 8

If argv[2]=2 Your program should output:

1 3 5 6 7 8

If argv[2]=3 Your program should output:

1 3 6 8 7 5