DESCRIPTION

     tsearch, tfind, twalk, and tdelete  manage  a  binary  tree.
     They  are  generalized  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
     integer 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  visited.  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.

RETURN VALUE

     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 entry.

WARNINGS

     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 reserve "postorder" to mean "after both  sub-
     trees".

     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 "endorder" or "leaf".  This works with the GNU
     library  implementation,  but  is not in the SysV documenta-
     tion.

EXAMPLE

     The following program inserts twelve random numbers  into  a
     binary  tree, then prints the numbers in order.  The numbers
     are removed from the tree and their storage freed during the
     traversal.

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

         void *root=NULL;

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

         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;
           void *val;

           switch(which)
             {
             case preorder:
               break;
             case postorder:
               datap = *(int **)nodep;
               printf("%6d\n", *datap);
               break;
             case endorder:
               datap = *(int **)nodep;
               (void)tdelete(datap, &root, compare);
               free(datap);
               break;
             case leaf:
               datap = *(int **)nodep;
               printf("%6d\n", *datap);
               val = tdelete(datap, &root, compare);
               free(datap);
               break;
             }
           return;
         }

         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;
         }

CONFORMING TO

     SVID

SEE ALSO

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