7.2 Data Types [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

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]