7.2 Data Types

We need two extra fields in the node structure to keep track of whether each link is a child pointer or a thread. Each of these fields is called a tag (see tag). The revised struct tbst_node, along with enum tbst_tag for tags, looks like this:

251. <TBST node structure 251> =
/* Characterizes a link as a child pointer or a thread. */
enum tbst_tag 
  {
    TBST_CHILD,                     /* Child pointer. */
    TBST_THREAD                     /* Thread. */
  };

/* A threaded binary search tree node. */
struct tbst_node 
  {
    struct tbst_node *tbst_link[2]; /* Subtrees. */
    void *tbst_data;                /* Pointer to data. */
    unsigned char tbst_tag[2];      /* Tag fields. */
  };

This code is included in 249.

Each element of tbst_tag[] is set to TBST_CHILD if the corresponding tbst_link[] element is a child pointer, or to TBST_THREAD if it is a thread. The other members of struct tbst_node should be familiar.

We also want a revised table structure, because traversers in threaded trees do not need a generation number:

252. <TBST table structure 252> =
/* Tree data structure. */
struct tbst_table 
  {
    struct tbst_node *tbst_root;        /* Tree's root. */
    tbst_comparison_func *tbst_compare; /* Comparison function. */
    void *tbst_param;                   /* Extra argument to tbst_compare. */
    struct libavl_allocator *tbst_alloc; /* Memory allocator. */
    size_t tbst_count;                  /* Number of items in tree. */
  };

This code is included in 249, 299, 335, 374, 417, 454, 488, 521, and 553.

There is no need to define a maximum height for TBST trees because none of the TBST functions use a stack.

Exercises:

1. We defined enum tbst_tag for distinguishing threads from child pointers, but declared the actual tag members as unsigned char instead. Why? [answer]