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 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>

Exercises:

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