Previous: Binary tree insertion, Up: Binary trees


14.6 Traversing a binary tree

— Function pointer: Bst_walk_f int (*) (void *data, void *params

The type of a function pointer used to perform arbitrary actions on an object in a bstree. The function is passed a pointer to an object, obj, as well as a user-supplied pointer to parameters, args.

For historical reasons, such a function should return an int; this was a bug in earlier versions which was not found and corrected in release 2.0 of Libretto. The value returned will be ignored, but the interface cannot be changed with making existing code incorrect.

— Function: void bst_walk (const Bstree *bst, Bst_walk_f walker, void *walk_args)

Calls walker on every node in chain in symmetric order (also called `inorder'). That is, for each node n, ‘bst_walk’ processes n's left subtree, then calls walker on n's data, and then processes n's right subtree. walk_args is passed as the last argument to walker.

— Function: void bst_walk_pre (const Bstree *bst, Bst_walk_f walker, void *walk_args)

Calls walker on every node in chain in pre-order. That is, for each node n, ‘bst_walk’ calls walker on n's data, then processes n's left subtree, and then processes n's right subtree. walk_args is passed as the last argument to walker.

— Function: void bst_walk_post (const Bstree *bst, Bst_walk_f walker, void *walk_args)

Calls walker on every node in chain in post-order. That is, for each node n, ‘bst_walk’ processes n's left subtree, then processes n's right subtree, and then calls walker on n's data. walk_args is passed as the last argument to walker.

— Function: Bstnode * bst_succ (const Bstree *bst, const Bstnode *node)
— Function: Bstnode * bst_pred (const Bstree *bst, const Bstnode *node)

Return the address of the successor or predecessor node respectively (in sorted order) of node, which must be a member of bst. If node is the largest or smallest respectively in bst, a null pointer is returned.

These routines are surprisingly efficient: they do not compare the data fields of nodes, nor do they store any state between calls. The intended usage models are:

          node = bst_smallest (bst);
          while (node != NULL) {
              /* do something with NODE->data */
              node = bst_succ (bst, node);
          }

and

          node = bst_largest (bst);
          while (node != NULL) {
              /* do something with NODE->data */
              node = bst_pred (bst, node);
          }

An access pattern of this form is quite efficient enough for all but the most time-critical code.