7.8.7 Advancing to the Next Node [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

Despite the earlier discussion (see Traversing a TBST), there are actually three cases, not two, in advancing within a threaded binary tree. The extra case turns up when the current node is the null item. We deal with that case by calling out to tbst_t_first().

Notice also that, below, in the case of following a thread we must check for a null node, but not in the case of following a child pointer.

275. <TBST traverser advance function 275> =
void *
tbst_t_next (struct tbst_traverser *trav)
{ assert (trav != NULL); if (trav->tbst_node == NULL) return tbst_t_first (trav, trav->tbst_table); else if (trav->tbst_node->tbst_tag[1] == TBST_THREAD)
    { trav->tbst_node = trav->tbst_node->tbst_link[1]; return trav->tbst_node != NULL ? trav->tbst_node->tbst_data : NULL; }
  else
    { trav->tbst_node = trav->tbst_node->tbst_link[1]; while (trav->tbst_node->tbst_tag[0] == TBST_CHILD) trav->tbst_node = trav->tbst_node->tbst_link[0]; return trav->tbst_node->tbst_data; } }

This code is included in 268.

See also:  [Knuth 1997], algorithm 2.3.1S.