In this project, you will implement a binary search tree in C. You will be able to use this any of the Keil board, Windows and in Linux.

This project will require you to create

• a source file containing the binary search tree data structure, and
• a file testing that structure.

At the end, we discuss marking.

You may wish to review the installation and environment of μVision, please see the Keil board web pages. Start with the first page and the installation, and you will have to understand main to finish this project. If you are interested, there is a Hello world! that you can do in the laboratory to print to the liquid-crystal display (LCD) panel.

Source file

This project will require:

• A header file (bst.hwe are providing together with a source file (bst.c) that you must implement (see the source files directory for this project.

You must additionally download the type.h file and place it in the same directory with the above files.

You will implement a binary search tree data structure where

• The binary search tree class stores the address of the root node and the number of nodes currently stored in the tree.
• Every node within the tree stores the addresses of both the left and right children (NULL if there is no child there) as well as the integer value stored in this node (of type S32).

This will require you to use two structures with appropriate type definitions bst_t and bsn_t. These are provided in the header file.

You will be required to modify the bst.c file to implement the following functions to manipulate the binary search tree with n nodes and a height h:

void bst_init( bst_t * );

Initialize the binary search tree so that it is empty. Run time: &Theta(1)

U32 bst_size();

Return the number of nodes in the binary search tree. Run time: &Theta(1)

bool bst_insert( bst_t *, S32 );

Insert the integer n into the binary search tree and return false if n is already in the tree (do not add a duplicate into the tree) and true otherwise. Ideally, such a function should not be implemented using recursion. See the marking scheme at the end. Run time: O(h)

S32 bst_min( bst_t * );

Returns the smallest integer in the binary search tree. Return INT_MAX if the tree is empty. Run time: O(h)

S32 bst_max( bst_t * );

Returns the largest integer in the binary search tree. Return INT_MIN if the tree is empty. Run time: O(h)

bool bst_erase( bst_t *, S32 );

If the object is in the binary search tree, remove it and return true; otherwise, return false and do nothing. Run time: O(h)

void bst_destroy( bst_t * );

Remove all nodes from this binary search tree. Run time: Θ(n) with Θ(n) memory. Note: Remember that you do not have to keep a search-tree structure while you are destroying the tree. If you maintain the search-tree structure, the run time will be O(n²). This run time is not required for 2014.

You are provided with a skeleton bst.c file. You are welcome to create other helper functions and you are welcome to add additional fields onto any of the records as you find necessary.

To use the type bool, you will have to also use #include <stdbool.h> at the top of your source file. You will have to use #include <limits.h> to access INT_MAX and INT_MIN.

Testing file

In a file called uwuserid_uwuserid_1.c, implement an instance of your structure as a local variable and add the following one hundred entries into your class.

You will require the following graphic LCD libraries:

• Graphics LCD library available here with a source file containing a .zip you can download.

First, you must understand how to create a skeleton main function for the Keil board.

	S32 value_array[100] = {
		 534, 6415,  465, 4459, 6869, 4442, 5840, 4180, 7450, 9265,
		  23, 2946, 3657, 3003,   29, 8922, 2199, 6973, 2344, 1802,
		9248, 5388, 2198, 2838, 1117, 5346, 4619, 8334, 9593, 2288,
		7346, 9252, 8169, 4138, 7479,  366, 5064, 6872,   -3, 8716,
		8089,   15, 5337, 8700, 8128, 6673, 5395, 7772, 5792, 3379,
		2438, 2184, 1176, 6083, 6572,  915, 1635, 6457, 3729, 7791,
		7642, 1548, 6267, 6562, 6477, 6026, 7460, 7226, 1994, 6519,
		7660, 3018, 2205,  559, 1347, 1647, 8778, 3864, 2543, 8370,
		1152,  865,  860, 8735, 4782,  574, 5858, 7089, 2096, 7449,
		1310, 3043, 8247, 6382, 2470, 3072, 1297, 7396, 7073,  140
	};

Next, print to the LED screen the minimum and maximum entries. Then, for each of the following set of 20 entries, erase those entries from your tree and again print the minimum and maximum entries.

	S32 erase_array[5][20] = {
		{ 915, 1802, 1994, 6083,  865, 8735, 6457, 8334, 4459, 3003,
		 2198, 2470, 7642,   15, 7772, 1152,   29, 2096,  574, 6415},

		{7396, 5858, 4442, 6872, 8128, 2838,  465, 6477, 8247, 6572,
		 2946, 1297, 3729, 4138, 5064, 8778, 4619, 5346,   -3, 3657},

		{1347, 2288, 7791, 7073, 5792, 3018,  366, 7449, 2543, 8089,
		 4180, 6026, 3864, 5395, 7226, 1117,   23, 7089, 1635, 6267},

		{8700, 3072, 7660, 6673, 2438, 3043, 1548, 4782, 6519, 7460,
		  559,  860, 6562, 9593, 1647, 1310, 3379, 8716, 8922, 7450},

		{9265, 6973, 8169, 5388,  140, 6869, 2344, 9252, 2184, 9248,
		  534, 2199, 6382, 7479, 8370, 7346, 5337, 5840, 2205, 1176}
	};

For your convenience, the minimum and maximum entries before each of these groups of twenty entries is erased from the tree are:

   Before first group is erased                -3,        9593
   After first group is erased                 -3,        9593
   After second group is erased                23,        9593
   After third group is erased                140,        9593
   After fourth group is erased               140,        9265
   When the tree is empty              2147483647, -2147483648

To print to the screen, you will have to use the printf function. Please see formatted printing and scanning for information on the use of this function, and printing to the LCD is described together with the GLCD header files.

A comment about local versus global variables

If the two array indicated above are declared as a local variable, both will occupy 400 bytes each and this memory will be allocated on the stack. The default stack size is 512 bytes; consequently, you have one of two options:

1. make the arrays global, or
2. increase the default stack size.

It is more efficient to make the arrays global, as in this case, the memory for those arrays is allocated once and resident in memory at one location; however, the data, unless declared constant, can be changed by any function using it (which, in this case, is not an issue). As a local variable, its contents must be copied onto the stack each time the function is called.

To learn about configuring the microprocessor, see configuring the Keil board.

Marking

Students will be working in groups of two and will be required to demonstrate that the function works as expected.

• First, you must submit your code on Learn. Either student may make the submission.
• Second, you will be required to convince the teaching assistant that you your code functions correctly (that is, you are not just writing a piece of code that prints six (6) pairs of numbers to the screen). If your code functions on the first attempt, you will receive 70. If your demonstration fails, and you are able to fix it within two minutes of the first failure, you will receive 60. If you cannot fix it, the instructor will review your code and grant a grade up to a maximum of 50. The time of your demonstration will be recorded, and will be compared to the time of the submission on Learn. If the times are out of order, the first offence will result in a penalty of -10, and the second offence will result in a penalty of -50.
• Third, 10 marks will be awarded for avoiding recursion in the bst_insert and bst_erase functions; again, you must demonstrate to the teaching assistant that your code uses iteration and not recursion.
• The remaining 20 marks will be based on comments and format of your submitted code. This will be marked by the course instructor. The course instructor will grade based on:
• Clarity and appropriateness of comments,
• Consistent coding style (you do not have to follow any particular coding style, but your commenting and coding style should be consisting), and
• Choice of variable names.