4.9.3.8 Backing Up to the Previous Node [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

Moving to the previous node is analogous to moving to the next node. The only difference, in fact, is that directions are reversed from left to right.

73. <BST traverser back up function 73> =
void *
bst_t_prev (struct bst_traverser *trav)
{ struct bst_node *x; assert (trav != NULL); if (trav->bst_generation != trav->bst_table->bst_generation) trav_refresh (trav); x = trav->bst_node; if (x == NULL)
    { return bst_t_last (trav, trav->bst_table); }
  else if (x->bst_link[0] != NULL)
    { if (trav->bst_height >= BST_MAX_HEIGHT)
        { bst_balance (trav->bst_table); return bst_t_prev (trav); } trav->bst_stack[trav->bst_height++] = x; x = x->bst_link[0]; while (x->bst_link[1] != NULL)
        { if (trav->bst_height >= BST_MAX_HEIGHT)
            { bst_balance (trav->bst_table); return bst_t_prev (trav); } trav->bst_stack[trav->bst_height++] = x; x = x->bst_link[1]; } }
  else
    { struct bst_node *y; do
        { if (trav->bst_height == 0)
            { trav->bst_node = NULL; return NULL; } y = x; x = trav->bst_stack[–trav->bst_height]; }
      while (y == x->bst_link[0]); } trav->bst_node = x; return x->bst_data; }

This code is included in 63.