Home
Main website
Display Sidebar
Hide Ads
Recent Changes
View Source:
tsearch(3)
Edit
PageHistory
Diff
Info
LikePages
TSEARCH !!!TSEARCH NAME SYNOPSIS DESCRIPTION RETURN VALUE WARNINGS EXAMPLE CONFORMING TO SEE ALSO ---- !!NAME tsearch, tfind, tdelete, twalk - manage a binary tree !!SYNOPSIS __#include __''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''__)); #ifdef _GNU_SOURCE typedef void (*__''__free_fn_t''__) (void *__''__nodep''__); void tdestroy (void *__''root''__, __free_fn_t__ ''free_content''__); #endif __ !!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 ''''.) The third argument is the depth of the node, with zero being the root. You should not modify the tree while traversing it as the the results would be undefined. __tdestroy__() removes the whole tree pointed to by ''rootp'', freeing all resources allocated by the __tsearch__() function. For the data in each tree node the function ''free_content'' is called. The pointer to the data is passed as the argument to the function. If no such work is necessary ''free_content'' must point to a function doing nothing. It is called in any case. !!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 __ __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 __ !!EXAMPLE The following program inserts twelve random numbers into a binary tree, then prints the numbers in order. Note that this example will collapse duplicate numbers. #include !!CONFORMING TO SVID, SUSv2 The __tdestroy__() function is a GNU extension, and it's only defined when the symbol ___GNU_SOURCE__ is defined before including ''''. !!SEE ALSO qsort(3), bsearch(3), hsearch(3), lsearch(3) ----
6 pages link to
tsearch(3)
:
Man3t
hcreate(3)
hdestroy(3)
hsearch(3)
lfind(3)
lsearch(3)
This page is a man page (or other imported legacy content). We are unable to automatically determine the license status of this page.
