tsearch, tdelete, twalk
Purpose
Manages binary search trees.
Library
Standard C Library (libc.a)
Syntax
#include <search.h>
char *tsearch ((char *) key, (char **) rootp, compar)
int (*compar) ( );
char *tdelete ((char *) key, (char **) rootp, compar)
int (*compar) ( );
void twalk ((char *) root, action)
void (*action) ( );
Description
The tsearch subroutine performs a binary tree search.
The algorithm is generalized from Donald E. Knuth's The
Art of Computer Programming, Volume 3, 6.2.2, Algorithm
T.(*) It returns a pointer into a tree indicating where
the data specified by the key parameter can be found. If
the data specified by the key parameter is not found, the
data is added to the tree in the correct place. If there
is not enough space available to create a new node, a
NULL pointer is returned. The rootp parameter points to
a variable that points to the root of the tree. If the
rootp parameter is NULL, the variable is set to point to
the root of a new tree.
The compar parameter is a pointer to the comparison func-
tion, which is called with two parameters that point to
the elements being compared. The comparison function
must compare its parameters and return a value as
follows:
o If the first parameter is less than the second param-
eter, compar must return a value less than 0.
o If the first parameter is equal to the second param-
eter, compar must return 0.
o If the first parameter is greater than the second
parameter, compar must return a value greater than 0.
---------------
(*) Reading, Massachusetts: Addison-Wesley, 1981.
The comparison function need not compare every byte, so
arbitrary data can be contained in the elements in addi-
tion to the values being compared.
If the rootp parameter is NULL on entry, then a NULL
pointer is returned.
The tdelete subroutine deletes the data specified by the
key parameter. It is generalized from Knuth (6.2.2)
Algorithm D. The rootp and compar parameters perform the
same function as they do for the tsearch subroutine. The
variable pointed to by the rootp parameter will be
changed if the deleted node is the root of the binary
tree. The tdelete subroutine returns a pointer to the
parent node of the deleted node. If the data is not
found, a NULL pointer is returned. If the rootp param-
eter is NULL on entry, then a NULL pointer is returned.
The twalk subroutine steps through the binary search tree
whose root is pointed to by the root parameter. (Any
node in a tree can be used as the root to step through
the tree below that node.) The action parameter is the
name of a routine to be invoked at each node. The
routine specified by the action parameter is called with
three parameters. The first parameter is the address of
the node currently being pointed to. The second param-
eter is a value from an enumeration data type
typedef enum {preorder, postorder, endorder, leaf} VISIT;
(This data type is defined in the search.h header file).
The actual value of the second parameter depends 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. A
leaf is a node that is not the parent of another node.
The third parameter is the level of the node in the tree,
with the root node being level zero.
The pointers to the key and the root of the tree should
be of type pointer-to-element and cast to type pointer-
to-character. Although declared as type pointer-to-
character, the value returned should be cast into type
pointer-to-element.
Related Information
In this book: "bsearch," "hsearch, hcreate, hdestroy,"
and "lsearch, lfind."