Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages


home | help
TSEARCH(3)		   Linux Programmer's Manual		    TSEARCH(3)

       tsearch,	tfind, tdelete,	twalk -	manage a binary	tree

       #include	<search.h>

       void *tsearch(const void	*key, void **rootp,
		       int(*compar)(const void *, const	void *));

       void *tfind(const void *key, const void **rootp,
		       int(*compar)(const void *, const	void *));

       void *tdelete(const void	*key, void **rootp,
		       int(*compar)(const void *, const	void *));

       void twalk(const	void *root, void(*action)(const	void *nodep,
					  const	VISIT which,
					  const	int depth));

       #define _GNU_SOURCE
       #include	<search.h>

       void tdestroy (void *root, void (*free_node)(void *nodep));

       tsearch,	tfind, twalk, and tdelete manage a binary tree.	 They are gen-
       eralized	from Knuth (6.2.2) Algorithm T.	 The first field in each  node
       of  the tree is a pointer to the	corresponding data item.  (The calling
       program must store the actual data.)  compar  points  to	 a  comparison
       routine,	 which takes pointers to two items.  It	should return an inte-
       ger which is negative, zero, or	positive,  depending  on  whether  the
       first item is less than,	equal to, or greater than the second.

       tsearch	searches  the  tree for	an item.  key points to	the item to be
       searched	for.  rootp points to a	variable which points to the  root  of
       the tree.  If the tree is empty,	then the variable that rootp points to
       should be set to	NULL.  If the item is found in the tree, then  tsearch
       returns a pointer to it.	 If it is not found, then tsearch adds it, and
       returns a pointer to the	newly added item.

       tfind is	like tsearch, except that if the item is not found, then tfind
       returns NULL.

       tdelete	deletes	 an item from the tree.	 Its arguments are the same as
       for tsearch.

       twalk performs depth-first, left-to-right traversal of a	 binary	 tree.
       root  points  to	 the starting node for the traversal.  If that node is
       not the root, then only part of the tree	will be	visited.  twalk	 calls
       the  user  function  action each	time a node is visited (that is, three
       times for an internal node, and once for	a  leaf).   action,  in	 turn,
       takes  three  arguments.	 The first is a	pointer	to the node being vis-
       ited.  The second is an integer which takes  on	the  values  preorder,
       postorder, and endorder depending on whether this is the	first, second,
       or third	visit to the internal node, or leaf if it is the single	 visit
       to  a leaf node.	 (These	symbols	are defined in _search.h_.)  The third
       argument	is the depth of	the node, with zero being the root.

       (More commonly, preorder, postorder, and	endorder  are  known  as  pre-
       order,  inorder,	and postorder: before visiting the children, after the
       first and before	the second, and	after visiting the children. Thus, the
       choice of name postorder	is rather confusing.)

       tdestroy	 removes  the  whole tree pointed to by	rootp, freeing all re-
       sources allocated by the	tsearch	function. For the data	in  each  tree
       node  the  function  free_node  is  called.  The	pointer	to the data is
       passed as the argument to the function. If no such  work	 is  necessary
       free_node must point to a function doing	nothing.

       tsearch	returns	 a  pointer  to	a matching item	in the tree, or	to the
       newly added item, or NULL if there was insufficient memory to  add  the
       item.   tfind  returns  a  pointer  to the item,	or NULL	if no match is
       found.  If there	are multiple elements that match the key, the  element
       returned	is unspecified.

       tdelete returns a pointer to the	parent of the item deleted, or NULL if
       the item	was not	found.

       tsearch,	tfind, and tdelete also	return NULL if rootp was NULL  on  en-

       twalk  takes  a	pointer	 to the	root, while the	other functions	take a
       pointer to a variable which points to the root.

       twalk uses postorder to mean "after the left subtree,  but  before  the
       right  subtree".	  Some	authorities would call this "inorder", and re-
       serve "postorder" to mean "after	both subtrees".

       tdelete frees the memory	required for the node in the tree.   The  user
       is responsible for freeing the memory for the corresponding data.

       The  example  program  depends  on the fact that	twalk makes no further
       reference to a node after calling the user function with	argument  "en-
       dorder" or "leaf".  This	works with the GNU library implementation, but
       is not in the SysV documentation.

       The following program inserts twelve random numbers into	a binary tree,
       where  duplicate	 numbers are collapsed,	then prints the	numbers	in or-

	   #include <search.h>
	   #include <stdlib.h>
	   #include <stdio.h>
	   #include <time.h>

	   void	*root=NULL;

	   void	*xmalloc(unsigned n) {
	     void *p;
	     p = malloc(n);
	     if(p) return p;
	     fprintf(stderr, "insufficient memory\n");

	   int compare(const void *pa, const void *pb) {
	     if(*(int *)pa < *(int *)pb) return	-1;
	     if(*(int *)pa > *(int *)pb) return	1;
	     return 0;

	   void	action(const void *nodep, const	VISIT which, const int depth) {
	     int *datap;

	     switch(which) {
	       case preorder:
	       case postorder:
		 datap = *(int **)nodep;
		 printf("%6d\n", *datap);
	       case endorder:
	       case leaf:
		 datap = *(int **)nodep;
		 printf("%6d\n", *datap);

	   int main() {
	     int i, *ptr;
	     void *val;

	     for (i = 0; i < 12; i++) {
		 ptr = (int *)xmalloc(sizeof(int));
		 *ptr =	rand()&0xff;
		 val = tsearch((void *)ptr, &root, compare);
		 if(val	== NULL) exit(1);
	     twalk(root, action);
	     return 0;

       SVID.  The function tdestroy() is a GNU extension.

       qsort(3), bsearch(3), hsearch(3), lsearch(3)

GNU				  1995-09-24			    TSEARCH(3)


Want to link to this manual page? Use this URL:

home | help