TSEARCH - search through binary tree.

(Compatible with UNIX System V C)

Usage:

#include <search.h>
char *tsearch();
ptr = tsearch( key, rootptr, compar);

Where:

char *key;

points to the key you are searching for. This can actually be any type of information, but the pointer must be cast into (char *).

char **rootptr;

points to a variable that points to the root of the tree. If "*rootptr" is NULL, the tree is empty. If "rootptr" itself is NULL, "tsearch" will return the NULL pointer.

int (*compar)(char *,char *);

is a pointer to a user-defined function that determines whether or not two keys are equal. This function should take two (char *) arguments; one will point to the key you want to find and the other will point to a key in the tree. The function should return a negative integer if the first argument is less than the second; it should return a positive integer if the first argument is greater than the second; and it should return zero if the two arguments are equal.

char *ptr;

points to a tree element that matches "key".

Description:

"tsearch" searches through a binary tree for a particular "key". It uses your "compar" function to compare the key to tree nodes. If the key is found, "tsearch" returns a pointer to it. If the key is not found, "tsearch" creates a new tree node for the key and returns a pointer to this new node.

The "compar" you use does not have to do a byte-by-byte comparison between the key and the tree nodes. For example, each key may be a C structure and "compar" may only look at a particular field when comparing two structures. In this case, the original search key might just be a dummy, with only the significant field filled in.

Each node in the tree is represented by a struct which contains pointers to adjacent tree nodes and to the data stored at the node. This struct is allocated with "malloc". If a new tree node cannot be allocated (e.g. because you are out of space), a NULL pointer will be returned. Note that the tree nodes do not contain the actual information: your program must store the data itself.

See Also:

expl c lib bsearch

expl c lib hsearch

expl c lib lsearch

expl c lib tfind

expl c lib tdelete

expl c lib twalk

Copyright © 1996, Thinkage Ltd.