TSEARCH(3)          Linux Programmer's Manual          TSEARCH(3)

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

SYNOPSIS
       #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));

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  func-
       tion  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 insuffi-
       cient memory to add the item.  tfind returns a pointer  to
       the item, or NULL if no match is found.  If there are mul-
       tiple 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 func-
       tions 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 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 "endorder" or "leaf".   This  works
       with  the  GNU  library  implementation, but is not in the
       SysV documentation.

EXAMPLE
       The following program inserts twelve random numbers into a
       binary  tree,  then prints the numbers in order.  The num-
       bers 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), lsearch(3)

GNU                     September 24, 1995                      1