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


GNU libavl 2.0.1

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

5.9.3.2 Starting at the First Node

To initialize a traverser to start at the least valued node, we simply descend from the root as far down and left as possible, recording the parent pointers on the stack as we go. If the stack overflows, then we balance the tree and start over.

 
void *
bst_t_first (struct bst_traverser *trav, struct bst_table *tree)
{ struct bst_node *x; assert (tree != NULL && trav != NULL); trav-&#62;bst_table = tree; trav-&#62;bst_height = 0; trav-&#62;bst_generation = tree-&#62;bst_generation; x = tree-&#62;bst_root; if (x != NULL) while (x-&#62;bst_link[0] != NULL)
{ if (trav-&#62;bst_height >= BST_MAX_HEIGHT)
{ bst_balance (tree); return bst_t_first (trav, tree); } trav-&#62;bst_stack[trav-&#62;bst_height++] = x; x = x-&#62;bst_link[0]; } trav-&#62;bst_node = x; return x != NULL ? x-&#62;bst_data : NULL; }
This code is included in @refalso{63

Exercises:

*1. Show that bst_t_first() will never make more than one recursive call to itself at a time. [answer]


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