4.2.1 Node Structure

When binary search trees were introduced in the last chapter, we used indexes into an array to reference items' smaller and larger values. But in C, BSTs are usually constructed using pointers. This is a more general technique, because pointers aren't restricted to references within a single array.

27. <BST node structure 27> =
/* A binary search tree node. */
struct bst_node 
  {
    struct bst_node *bst_link[2];   /* Subtrees. */
    void *bst_data;                 /* Pointer to data. */
  };

This code is included in 25.

In struct bst_node, bst_link[0] takes the place of smaller, and bst_link[1] takes the place of larger. If, in our array implementation of binary search trees, either of these would have pointed to the sentinel, it instead is assigned NULL, the null pointer constant.

In addition, bst_data replaces value. We use a void * generic pointer here, instead of int as used in the last chapter, to let any kind of data be stored in the BST. See Comparison Function, for more information on void * pointers.