www.delorie.com/gnu/docs/avl/libavl_144.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

8.8.7 Advancing to the Next Node

Despite the earlier discussion (see section 8.8 Traversal), 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.

 
void *
tbst_t_next (struct tbst_traverser *trav)
{ assert (trav != NULL); if (trav-&#62;tbst_node == NULL) return tbst_t_first (trav, trav-&#62;tbst_table); else if (trav-&#62;tbst_node-&#62;tbst_tag[1] == TBST_THREAD)
{ trav-&#62;tbst_node = trav-&#62;tbst_node-&#62;tbst_link[1]; return trav-&#62;tbst_node != NULL ? trav-&#62;tbst_node-&#62;tbst_data : NULL; }
else
{ trav-&#62;tbst_node = trav-&#62;tbst_node-&#62;tbst_link[1]; while (trav-&#62;tbst_node-&#62;tbst_tag[0] == TBST_CHILD) trav-&#62;tbst_node = trav-&#62;tbst_node-&#62;tbst_link[0]; return trav-&#62;tbst_node-&#62;tbst_data; } }
This code is included in @refalso{268

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


  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003