tsearch.3

来自「<B>Digital的Unix操作系统VAX 4.2源码</B>」· 3 代码 · 共 186 行

.\" SCCSID: @(#)tsearch.3	8.1	9/11/90
.TH tsearch 3 
.SH Name
tsearch, tfind, tdelete, twalk \- manage binary search trees
.SH Syntax
.B #include <search.h>
.PP
.B void *tsearch (\fIkey, rootp, compar\fP)
.br
.B void *\fIkey\fP;
.br
.B void **\fIrootp\fP;
.br
.B int (*\fIcompar\fP)\^( )\^;
.PP
.B void *tfind (\fIkey, rootp, compar\fP)
.br
.B void *\fIkey\fP;
.br
.B void **\fIrootp\fP;
.br
.B int (*\fIcompar\fP)\^( )\^;
.PP
.B void *tdelete (\fIkey, rootp, compar\fP)
.br
.B void *\fIkey\fP;
.br
.B void **\fIrootp\fP;
.br
.B int (*\fIcompar\fP)\^( )\^;
.PP
.B void twalk (\fIroot, action\fP)
.br
.B void * \fIroot\fP;
.br
.B void (*\fIaction\fP)\^( )\^;
.SH Description
.NXR "tsearch subroutine"
.NXR "tfind subroutine"
.NXR "tdelete subroutine"
.NXR "twalk subroutine"
.NXR "binary search routine" "managing tree searches"
The
.PN tsearch
subroutine
is a binary tree search routine
generalized from Knuth (6.2.2) Algorithm T.
It returns a pointer into a tree indicating where
a datum may be found.
If the datum does not occur, it is added
at an appropriate point in the tree.
The
.I key\^
points to the datum to be sought in the tree.
The
.I rootp\^
points to a variable that points to the root
of the tree.
A NULL
pointer value for the variable denotes an empty tree;
in this case,
the variable will be set to point to the datum at the root
of the new tree.  The
.I compar
is the name of the comparison function.
It is called with two arguments that point
to the elements being compared.
The function must return
an integer less than, equal to, or greater than zero
according as the first argument is to be considered
less than, equal to, or greater than the second.
.PP
Like 
.PN tsearch ,
.PN tfind
will search for a datum in the tree,
returning a pointer to it if found.  However, if it is not found,
.PN tfind
will return a NULL pointer.  The arguments for 
.PN tfind
are the same as for 
.PN tsearch .
.PP
The
.PN tdelete
subroutine deletes a node from a binary search tree.
It is generalized from Knuth (6.2.2)
algorithm D.
The arguments are the same as for 
.PN tsearch .
The variable pointed to by
.I rootp\^
will be changed if the deleted node was the root of the tree.
The
.PN tdelete
subroutine returns a pointer to the parent of the deleted node,
or a NULL pointer if the node is not found.
.PP
The
.PN twalk
subroutine traverses a binary search tree.
The
.I root
is the root of the tree to be traversed.
(Any node in a tree may be used as the root for a walk below that node.)
The
.I action
is the name of a routine
to be invoked at each node.
This routine is, in turn,
called with three arguments.
The first argument is the address of the node being visited.
The second argument is a value from an enumeration data type
.I "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.
The third argument is the level of the node
in the tree, with the root being level zero.
.NT "Notes"
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.
.sp
The comparison function need not compare every byte,
so arbitrary data
may be contained in the elements in addition to the values
being compared.
.sp
Although declared as type pointer-to-character,
the value returned should be cast into type pointer-to-element.
.sp
Note that the
.I root
argument to 
.PN twalk
is one level of indirection less than the
.I rootp
arguments to
.PN tsearch
and
.PN tdelete .
.NE
.SH Return Values
A NULL pointer is returned by 
.PN tsearch
if there
is not enough space available to create a new node.
.br
A NULL pointer is returned by
.PN tsearch ,
.PN tfind ,
and
.PN tdelete
if \fIrootp\fP is NULL on entry.
.br
If the datum is found, both 
.PN tsearch
and
.PN tfind
return a pointer to it.  If not, 
.PN tfind
returns NULL,
and 
.PN tsearch
returns a pointer to the inserted item.
.SH Restrictions
.NXR "tsearch subroutine" "restrictions"
Results are unpredictable if the calling
function alters the pointer to the root.
.SH Diagnostics
.NXR "tsearch subroutine" "diagnostics"
A NULL
pointer is returned by
.PN tsearch
and
.PN tdelete
if
.I rootp\^
is NULL on entry.
.SH See Also
bsearch(3), hsearch(3), lsearch(3)