HP C/iX Library Reference Manual (30026-90004)

Chapter 5 375
HP C/iX Library Function Descriptions
twalk
twalk
Traverses a binary search tree and returns the value at the specified node.
Syntax
#include <search.h>
void *twalk (void * root , void *( action )( ));
Parameters
root A pointer to the starting node for the tree traversal.
action The name of a user-supplied function to be invoked at each node.
Return Values
None.
Description
The twalk function performs a depth-first, left-to-right traversal of a binary search tree.
The tdelete, tfind, tsearch, and twalk functions manage binary search trees
generalized from Knuth Algorithms T and D (6.2.2).
1
Any node in the tree can be used as the root for a walk below that node.
The pointer to the root of the tree should be of type pointer-to-element, and cast to type
pointer-to-character. Similarly, although declared as type pointer-to-character, the value
returned should be cast into type pointer-to- element.
The
root argument to twalk() is one level of indirection less than the rootp arguments to
tsearch() and tdelete().
The
action function supplied by the calling program is invoked at each node. This
function is, in turn, called with three arguments.
void action_routine (struct ** node , visit order , int level )
The first argument is the address of the node being visited.
The second argument is a value from an enumeration data type:
typedef enum { preorder, postorder, endorder, leaf } VISIT;
defined in the <search.h> header file, depending on whether this is the first, second or
third time that the node has been visited during a depth- first, left-to-right traversal of the
tree, or whether the node is a leaf.
There are two nomenclatures used to refer to the order in which tree nodes are visited.
This implementation uses preorder, postorder and endorder to respectively refer to visiting
1. The Art of Computer Programming, Vol3 (Sorting and Searching) by Donald Ervin Knuth (Reading,
Mass.:Addison-Wesley, 1973).