tsearch, tfind, tdelete, twalk - manage binary search trees


     #include <search.h>

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

     void *tfind(const  void  *key,  void  *  const  *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) (void  *,  VISIT,


     The tsearch(), tfind(), tdelete(), and twalk() functions are
     routines for manipulating binary search trees. They are gen-
     eralized from  Knuth (6.2.2) Algorithms T and  D.  All  com-
     parisons 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 ele-
     ments in addition to the values being compared.

     The tsearch() function is used to build and access the tree.
     The  key  argument 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 key), 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. The rootp argument points to a variable
     that  points  to  the root of the tree. A null value for the
     variable pointed to by rootp 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.

     Like tsearch(), tfind() will search for a datum in the tree,
     returning  a  pointer  to it if found. However, if it is not
     found, tfind() will return a null pointer. The arguments for
     tfind() are the same as for tsearch().

     The tdelete() function deletes a node from a  binary  search
     tree.  The  arguments  are  the  same as for  tsearch(). The
     variable pointed to by rootp will be changed if the  deleted
     node  was  the root of the tree. tdelete() returns a pointer
     to the parent of the deleted node, or a null pointer if  the
     node is not found.

     The twalk() function traverses a  binary  search  tree.  The
     root  argument 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.) 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

          typedef enum { preorder, postorder,  endorder,  leaf  }

     (defined in <search.h>), 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

     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


     If the node is found, both tsearch() and  tfind()  return  a
     pointer  to it.  If not, tfind() returns a null pointer, and
     tsearch() returns a pointer to the inserted item.

     A null pointer is returned by  tsearch()  if  there  is  not
     enough space available to create a new node.

     A  null  pointer  is  returned  by  tsearch(),  tfind()  and
     tdelete() if rootp is a null pointer on entry.

     The tdelete() function returns a pointer to  the  parent  of
     the  deleted  node,  or  a  null  pointer if the node is not

     The twalk() function returns no value.


     No errors are defined.


     The root argument to  twalk() is one  level  of  indirection
     less than the rootp arguments to tsearch() and tdelete().

     There are two nomenclatures used to refer to  the  order  in
     which  tree nodes are visited. tsearch() uses preorder, pos-
     torder 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.

     If the calling function alters  the  pointer  to  the  root,
     results are unpredictable.


     Example 1: A sample program of using tsearch function.

     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.

     #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(const 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);

             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;
             twalk(root, print_node);


     See attributes(5) for descriptions of the  following  attri-

    |       ATTRIBUTE TYPE        |       ATTRIBUTE VALUE       |
    | MT-Level                    | Safe                        |


     bsearch(3C), hsearch(3C), lsearch(3C), attributes(5)

Man(1) output converted with man2html