4 Binary Search Trees [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

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 25> and an implementation file <bst.c 26>, 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. 

25. <bst.h 25> =
<Library License 1>
#ifndef BST_H
#define BST_H 1

#include <stddef.h>

<Table types; tbl => bst 15>
<BST maximum height 29>
<BST table structure 28>
<BST node structure 27>
<BST traverser structure 62>
<Table function prototypes; tbl => bst 16>
<BST extra function prototypes 89>

#endif /* bst.h */

<Table assertion function control directives; tbl => bst 595>


26. <bst.c 26> =
<Library License 1>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "bst.h"

<BST operations 30>

Exercises:

1. What is the purpose of #ifndef BST_H ... #endif in <bst.h 25> above? [answer]