Files talked about:

int-bst.h.:

/******************************************************************************* * * simple implementation of binary search tree of ints * * "tree" is represented by pointer to root node */ /* * the next two directives (and the last line) make the .h file "idempotent" -- * if you inadvertently #include it twice, no harm done, * since the second #include finds SORTED_INT_LIST_H defined * and ignores the rest of the file. * this is (usually?) considered to be good style. */ #ifndef INT_BST_H #define INT_BST_H #include #include #include /* * data structure for tree node * * type to use in declaring nodes, and pointers to nodes, * is int_bst_node_t */ typedef struct int_bst_node { int data; struct int_bst_node * left; struct int_bst_node * right; } int_bst_node_t; /* * functions * * notice that functions that might change the head of a list take as a * parameter a int_bst_node_t ** (pointer to pointer to node). * so that if called with the address of a variable they can change it. */ /* * insert n into *t_p * does nothing if n is already in the tree * returns true if insertion succeeded (including the case where n is already * in the tree), false otherwise (e.g., malloc error) */ bool int_bst_insert(int_bst_node_t ** t_p, int n); /* * find n in t */ bool int_bst_find(int_bst_node_t * t, int n); /* * remove n from *t_p * OPTIONAL operation -- your code can just print an error message * and otherwise do nothing */ void int_bst_remove(int_bst_node_t ** t_p, int n); /* * remove all nodes from *t_p and set (*t_p) to NULL */ void int_bst_remove_all(int_bst_node_t ** t_p); /* * print all elements of t to output stream f using format fmt * ("fmt" is the kind of string expected by fprintf, e.g., "%d " or "%d ") * * the FILE * parameter lets the caller decide whether to print * to stdout or a file (already open) or what * the fmt parameter lets the caller decide whether to print all on * one line or each on a separate line or what */ void int_bst_print_elements(int_bst_node_t * t, FILE * f, char * fmt); /* * print all elements of t to output stream f in tree form * (see sample output for one way to do this -- or you may have * a better idea) */ void int_bst_print_as_tree(int_bst_node_t * t, FILE * f); #endif /* end of ifndef INT_BST_H */

int-bst.c.:

#include "int-bst.h" /* YOUR CODE GOES HERE */

Makefile.:

# # makefile for binary search tree # # 'make test-int-bst' makes the executable # (so does 'make main') # # 'make OPT= test-int-bst makes the executable # with a non-default optimization level # (possible values are -g, -O0, etc.) # 'make clean' deletes object files # 'make xclean' deletes object files and executable # # to use valgrind to check for memory leaks and other malloc/free errors: # 'make OPT="-g -O0" test-int-bst # 'valgrind test-int-bst' # OPT = -O CFLAGS = -Wall -pedantic -std=c99 $(OPT) EXE = test-int-bst OBJS = test-int-bst.o test-helper.o int-bst.o main: $(EXE) $(EXE): $(OBJS) gcc $(CFLAGS) -o $(EXE) $(OBJS) test-int-bst.o: test-int-bst.c int-bst.h test-helper.o: test-helper.c test-helper.h int-bst.o: int-bst.c int-bst.h .PHONY: clean clean: -rm $(OBJS) .PHONY: xclean xclean: -rm $(OBJS) $(EXE) 

test-int-bst.c, :

/* * test program for sorted list of ints * no inputs */ #include #include #include "int-bst.h" #include "test-helper.h" /******************************************************************************* * * declarations (prototypes) of helper functions * "static" so not visible outside this file */ /* convenience functions to print tree */ static void print_tree_elements(int_bst_node_t * t); static void print_tree_as_tree(int_bst_node_t * t); /* functions to test BST functions verbosely */ static void test_insert(int_bst_node_t ** t_p, int n); static void test_remove(int_bst_node_t ** t_p, int n); static void test_find(int_bst_node_t * t, int n); /******************************************************************************* * * main program */ int main(void) { int_bst_node_t * tree_p = NULL; int insert_data[] = { 40, 30, 50, 20, 60, 16, 14, 18, 24, 56, 64, 30, 50 }; int find_data[] = { 0, 100, 10, 40, 14, 64 }; int remove_data[] = { 0, 16, 60, 30, 50 }; for (int i = 0; i  
test-helper.c
 
/******************************************************************************* * * definitions (implementation) of functions declared in .h file * (plus helper functions) * */ #include #include /* * helper functions (static so not visible outside this file) */ static int int_compare(const void * e1, const void * e2) { int * i1 = (int *) e1; int * i2 = (int *) e2; if (*i1  *i2) return 1; else return 0; } /* * functions declared in .h file */ void print_test_data(int data[], size_t sz) { int sorted[sz]; for (int i = 0; i  
test-helper.h.:
 
/******************************************************************************* * * helper functions for test program * * (why in a separate file? might be useful with other test programs) */ #ifndef TEST_HELPER_H #define TEST_HELPER_H /* function to display test data in sorted order */ void print_test_data(int data[], size_t sz); #endif /* ifndef TEST_HELPER_H */ 
  Programming Problems Do the following programming problems. You will end up with at least one code file per problem. Submit your program source (and any other needed files) by sending mail to bmassing cs.trinity.edu with each file as an attachment. Please use a subject line that mentions the course and the assignment (e.g., csci 1120 hw 9" or "LL hw 9"). You can develop your programs on any system that provides the needed functionality, but I will test them on one of the department's Linux machines, so you should probably make sure they work in that environment before turning them in. 1. (20 points) Your mission for this assignment is to complete a partial implementation in C of a binary search tree (a.k.a. sorted binary tree) of ints. (I'm hoping that all of you know about this data structure from CS2 or another course. If not, the Wikipedia article is a reasonable description (but I recommend that you not read the example code until you try to write your own). This partial implementation consists of a number of files: o Function declarations for tree: int-bst.h. o Starter file for function definitions: int-bst.c. o Test program and supporting files: test-int-bst.c, test-helper.c, test-helper.h. o Makefile for compiling (comments in the file tell you how to use it): Makefile. I've made a ZIP file containing all of these files, so it will probably be simplest just to download that and unzip it (command unzip on our machines). If you prefer to download individual files, NOTE that you should use your browser's download" or "save" function to obtain the Makefile rather than copying and pasting text. This is because copy-and-paste will likely replace the tab characters in the file with spaces, with bad consequences (since tabs are semantically significant in makefiles.) Your job is to modify the file int-bst.c so it includes function definitions for all the functions declared in int-bst.h. The test program is self-contained and contains code to call the functions you will write, so you don't need to write any input/output code, aside from implementing two print functions. You compile the test program by typing make test-int-bst and run it by typing test- int-bst. Notice that the function that removes a single element of the tree (int_bst_remove) is optional -- you can provide an actually implement this operation. implementation" that just prints an error message, or for extra credit you can You should not modify any other files, unless you want to add additional tests to test-int-bot.c. Sample output of the test program