HP 3000 Manuals HP 3000 Manuals
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)
FOOTNOTE (1) The Art of Computer Programming, Vol3 (Sorting
and Searching) by Donald Ervin Knuth (Reading,
Mass.:Addison-Wesley, 1973).
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 a node before any of its
children, after its left child and before its right, and after both its
children. The alternate nomenclature uses preorder, inorder, and
postorder to refer to the same visits, which results in some confusion
over the meaning of postorder.
The third argument is the level of the node in the tree, with the root
being level zero.
NOTE The twalk function and the header file <search.h> are not part of
ANSI C. Using them makes your program less portable.
Examples
Refer to the example located in the tsearch() function description.
See Also
tfind(), tsearch(), tdelete()