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

Syntax	#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) (const void *, VISIT, int));
Description	tsearch(), tfind(), tdelete() and twalk() manipulate binary search trees. Comparisons are made with a user-supplied compar function. This function is called with two arguments, the pointers to the elements being compared. It returns an integer less than, equal to or greater than 0, depending on whether the first argument is 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 elements in addition to the values being compared. tsearch() is used to build and access the tree. The key argument is a pointer to an element to be accessed or stored. If there is an entry in the tree that is equal to *key (the value pointed to by the key), a pointer to this found entry is returned. Otherwise, *key is inserted, and a pointer to it is 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 pointer value for the variable pointed to by rootp denotes an empty tree; in this case, the variable is set to point to the entry that appears at the root of the new tree. Like tsearch(), the tfind() function searches for an entry in the tree and returns a pointer to it if found. If the entry is not found, the tfind() function returns a null pointer. The arguments for tfind() are the same as for tsearch(). tdelete() deletes a node from a binary search tree. The arguments are the same as for tsearch(). The variable to which rootp points is changed if the deleted node was the root of the tree. The tdelete() function returns a pointer to the parent of the deleted node, or a null pointer if the node is not found. twalk() traverses a binary search tree. The root argument is a pointer to 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 function to be invoked at each node. This function is called with three arguments. The first argument is the address of the node being visited. The structure pointed to by this argument is unspecified and must not be modified; however, the value of type "pointer-to-node" can be converted to the type "pointer-to-pointer-to-element" to access the element stored in the node. The second argument is a value from the enumeration data type typedef enum { preorder, postorder, endorder, leaf } VISIT; (defined in the header search.h), depending on whether this is the first, second or third time that the node is 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 0.
Returnval	Pointer to the found node
		tsearch() and tfind(), if *key was found.
	Pointer to the inserted node
		tsearch(), if *key was not found, but could be inserted.
	Null pointer	tsearch(), if there is not enough space available to create a new node. tsearch(), tfind() and tdelete(), if rootp is a null pointer on entry. tfind(), if *key was not found.
	Pointer to the parent of the deleted node
		tdelete(), if successful.
Notes	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. The tsearch() function uses preorder, postorder and endorder to refer, respectively, to visiting a node before any of its children, visiting it after its left child and before its right, and visiting a node after both its children. The alternative 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, the results are unpredictable.
See also	bsearch(), hsearch(), lsearch(), search.h.