www.delorie.com/gnu/docs/avl/libavl_50.html

search

	Buy GNU books!

GNU libavl 2.0.1

5.9.2.1 Improving Convenience

Now we can work on improving the convenience of our traversal function. But, first, perhaps it's worthwhile to demonstrate how inconvenient it really can be to use walk(), regardless of how it's implemented internally.

Suppose that we have a BST of character strings and, for whatever reason, want to know the total length of all the strings in it. We could do it like this using walk():

static void process_node (void *data, void *param) { const char *string = data; size_t *total = param; *total += strlen (string); } size_t total_length (struct bst_table *tree) { size_t total = 0; walk (tree, process_node, &total); return total; }

With the functions first_item() and next_item() that we'll write in this section, we can rewrite these functions as the single function below:

size_t total_length (struct bst_table *tree) { struct traverser t; const char *string; size_t total = 0; for (string = first_item (tree, &t); string != NULL; string = next_item (&t)) total += strlen (string); return total; }

You're free to make your own assessment, of course, but many programmers prefer the latter because of its greater brevity and fewer "unsafe" conversions to and from void pointers.

Now to actually write the code. Our task is to modify traverse_iterative() so that, instead of calling action, it returns node->bst_data. But first, some infrastructure. We define a structure to contain the state of the traversal, equivalent to the relevant argument and local variables in traverse_iterative(). To emphasize that this is not our final version of this structure or the related code, we will call it struct traverser, without any name prefix:

struct traverser { struct bst_table *table; /* Tree being traversed. */ struct bst_node *node; /* Current node in tree. */ struct bst_node *stack[BST_MAX_HEIGHT]; /* Parent nodes to revisit. */ size_t height; /* Number of nodes in stack. */ };

See also @refalso{59

Function first_item() just initializes a struct traverser and returns the first item in the tree, deferring most of its work to next_item():

/* Initializes trav for tree. Returns data item in tree with the smallest value, or NULL if tree is empty. In the former case, next_item() may be called with trav to retrieve additional data items. */ void * first_item (struct bst_table *tree, struct traverser *trav) { assert (tree != NULL && trav != NULL); trav->table = tree; trav->node = tree->bst_root; trav->height = 0; return next_item (trav); }

Function next_item() is, for the most part, a simple modification of traverse_iterative():

/* Returns the next data item in inorder within the tree being traversed with trav, or if there are no more data items returns NULL. In the former case next_item() may be called again to retrieve the next item. */ void * next_item (struct traverser *trav) { struct bst_node *node; assert (trav != NULL); node = trav->node; while (node != NULL) { if (trav->height >= BST_MAX_HEIGHT) { fprintf (stderr, "treetoodeep\n"); exit (EXIT_FAILURE); } trav->stack[trav->height++] = node; node = node->bst_link[0]; } if (trav->height == 0) return NULL; node = trav->stack[--trav->height]; trav->node = node->bst_link[1]; return node->bst_data; }

See also: [ Knuth 1997], algorithm 2.3.1T; [ Knuth 1992], p. 50--54, section "Recursion Elimination" within article "Structured Programming with go to statements".

Exercises:

1. Make next_item() reliable by providing alternate code to execute on stack overflow. This code will work by calling bst_balance() to "balance" the tree, reducing its height such that it can be traversed with the small stack that we use. We will develop bst_balance() later. For now, consider it a "black box" that simply needs to be invoked with the tree to balance as an argument. Don't forget to adjust the traverser structure so that later calls will work properly, too. [answer]

2. Without modifying next_item() or first_item(), can a function prev_item() be written that will move to and return the previous item in the tree in inorder? [answer]