|4 Binary Search Trees|
The previous chapter motivated the need for binary search trees. This chapter implements a table ADT backed by a binary search tree. Along the way, we'll see how binary search trees are constructed and manipulated in abstract terms as well as in concrete C code.
The library includes a header file <bst.h 24> and an implementation file <bst.c 25>, outlined below. We borrow most of the header file from the generic table headers designed a couple of chapters back, simply replacing tbl by bst, the prefix used in this table module.
24. <bst.h 24> = <License 1> #ifndef BST_H #define BST_H 1 #include <stddef.h> <Table types; tbl => bst 14> <BST maximum height 28> <BST table structure 27> <BST node structure 26> <BST traverser structure 61> <Table function prototypes; tbl => bst 15> <BST extra function prototypes 88> #endif /* bst.h */ <Table assertion function control directives; tbl => bst 593>
25. <bst.c 25> = <License 1> #include <assert.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include "bst.h" <BST operations 29>
1. What is the purpose of #ifndef BST_H ... #endif in <bst.h 24> above? [answer]