7.8.7 Advancing to the Next Node

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.