'\"macro stdmacro
.if n .pH g3c.tsearch @(#)tsearch	40.11 of 10/27/89
.\" Copyright 1989 AT&T
.nr X
.if \nX=0 .ds x} tsearch 3C "C Programming Language Utilities" "\&"
.if \nX=1 .ds x} tsearch 3C "C Programming Language Utilities"
.if \nX=2 .ds x} tsearch 3C "" "\&"
.if \nX=3 .ds x} tsearch "" "" "\&"
.TH \*(x}
.SH NAME
\f4tsearch\f1, \f4tfind\f1, \f4tdelete\f1, \f4twalk\f1 \- manage binary search trees
.SH SYNOPSIS
.nf
\f4#include <search.h>\f1
.PP
\f4void \(**tsearch (const void \(**key, void \(**\(**rootp, \f4int (\(**compar) 
    (const void \(**, const void \(**));\f1
.PP
\f4void \(**tfind (const void \(**key, void \(** const \(**rootp, \f4int (\(**compar)
    (const void \(**, const void \(**));\f1
.PP
\f4void \(**tdelete (const void \(**key, void \(**\(**rootp, \f4int (\(**compar)
    (const void \(**, const void \(**));\f1
.PP
\f4void twalk (void \(**root, void(\(**action) (void \(**, VISIT, int));\f1
.SH DESCRIPTION
\f4tsearch,\fP
\f4tfind,\fP
\f4tdelete,\fP
and
\f4twalk\fP
are routines for manipulating binary search trees.
They are generalized from Knuth (6.2.2) Algorithms T and D.
All comparisons are done with a user-supplied routine.
This routine is called with two arguments,
the pointers to the elements being compared.
It returns an integer less than, equal to,
or greater than 0, according to whether the first argument
is to be considered less than, equal to or greater than the
second argument.
The comparison function need not compare every byte,
so arbitrary data may be contained in the elements
in addition to the values
being compared.
.PP
\f4tsearch\fP
is used to build and access the tree.
\f2key\f1
is a pointer to a datum to be accessed or stored.
If there is a datum in the tree
equal to \(**key (the value pointed to by \f2key\fP),
a pointer to this found
datum is returned.
Otherwise, \(**key is inserted, and a pointer to it
returned.
Only pointers are copied, so the calling routine must
store the data.
\f2rootp\^\f1
points to a variable that points to the root
of the tree.
A
\f4NULL\fP
value for the variable pointed to by
\f2rootp\f1
denotes an empty tree;
in this case,
the variable will be set to point to the datum
which will be at the root of the new tree.
.PP
Like
\f4tsearch\fP,
\f4tfind\fP
will search for a datum in the tree, returning a pointer
to it if found.
However, if it is not found,
\f4tfind\fP
will return a
\f4NULL\fP
pointer.
The arguments for
\f4tfind\fP
are the same as for
\f4tsearch\fP.
.PP
\f4tdelete\fP
deletes a node from a binary search tree.
The arguments are the same as for 
\f4tsearch\fP.
The variable pointed to by
\f2rootp\^\f1
will be changed if the deleted node was the root of the tree.
\f4tdelete\fP
returns a pointer to the parent of the deleted node,
or a
\f4NULL\fP
pointer if the node is not found.
.PP
\f4twalk\fP
traverses a binary search tree.
\f2root\^\f1
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.)
.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 }"
.SM
.I VISIT;
(defined in the 
\f4search.h\fP
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.
.PP
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.
Similarly, although declared as type pointer-to-character,
the value returned should be cast into type pointer-to-element.
.SH EXAMPLE
The following code reads in strings and
stores structures containing a pointer to each string
and a count of its length.
It then walks the tree, printing out the stored strings
and their lengths in alphabetical order.
.P
.nf
.ft CW
#include <string.h>
#include <stdio.h>
#include <search.h>

struct node {
	char *string;
	int length;
};
char string_space[10000];
struct node nodes[500];
void *root = NULL;

int node_compare(const void *node1, const void *node2) {
	return strcmp(((const struct node *) node1)->string,
		      ((const struct node *) node2)->string);
}

void print_node(void **node, VISIT order, int level) {
	if (order == preorder || order == leaf) {
		printf("length=%d, string=%20s\\n",
		(*(struct node **)node)->length,
		(*(struct node **)node)->string);
	}
}

main() {
	char *strptr = string_space;
	struct node *nodeptr = nodes;
	int i = 0;

	while (gets(strptr) != NULL && i++ < 500) {
		nodeptr->string = strptr;
		nodeptr->length = strlen(strptr);
		(void) tsearch((void *)nodeptr,
				&root, node_compare);
		strptr += nodeptr->length + 1;
		nodeptr++;
	}
	twalk(root, print_node);
}
.ft 1
.fi
.SH SEE ALSO
\f4bsearch\fP(3C), \f4hsearch\fP(3C), \f4lsearch\fP(3C).
.SH DIAGNOSTICS
A
\f4NULL\fP
pointer is returned by 
\f4tsearch\fP
if there is not enough space available to create a new node.
.sp .2
A
\f4NULL\fP
pointer is returned by
\f4tfind\fP
and
\f4tdelete\fP
if
\f2rootp\^\f1
is
\f4NULL\fP
on entry.
.sp .2
If the datum is found, both 
\f4tsearch\fP
and 
\f4tfind\fP
return a pointer to it.
If not, 
\f4tfind\fP
returns \f4NULL,\fP and 
\f4tsearch\fP
returns a pointer to the inserted
item.
.SH NOTES
The
\f4root\^\f1
argument to 
\f4twalk\fP
is one level of indirection less than the
\f2rootp\^\f1
arguments to
\f4tsearch\fP
and
\f4tdelete\fP.
.sp .2
There are two nomenclatures used to refer to the order in which
tree nodes are visited.
\f4tsearch\fP
uses preorder, postorder and endorder to refer respectively 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 could result in some confusion over
the meaning of postorder.
.PP
If the calling function alters the pointer to the
root, results are unpredictable.
.\"	@(#)tsearch.3c	6.3 of 10/20/83
.Ee
