Search:

TSEARCH(3) DragonFly Library Functions Manual TSEARCH(3)## NAME

tsearch,tfind,tdelete,twalk-- manipulate binary search trees## LIBRARY

Standard C Library (libc, -lc)## SYNOPSIS

#include<search.h>void*tdelete(constvoid*restrictkey,void**restrictrootp,int(*compar)(constvoid*,constvoid*));void*tfind(constvoid*key,void*const*rootp,int(*compar)(constvoid*,constvoid*));void*tsearch(constvoid*key,void**rootp,int(*compar)(constvoid*,constvoid*));voidtwalk(constvoid*root,void(*action)(constvoid*,VISIT,int));## DESCRIPTION

Thetdelete(),tfind(),tsearch(), andtwalk() functions manage binary search trees based on algorithms T and D from Knuth (6.2.2). The compar- ison function passed in by the user has the same style of return values as strcmp(3). Thetfind() function searches for the datum matched by the argumentkeyin the binary tree rooted atrootp, returning a pointer to the datum if it is found and NULL if it is not. Thetsearch() function is identical totfind() except that if no match is found,keyis inserted into the tree and a pointer to it is returned. Ifrootppoints to a NULL value a new binary search tree is created. Thetdelete() function deletes a node from the specified binary search tree and returns a pointer to the parent of the node to be deleted. It takes the same arguments astfind() andtsearch(). If the node to be deleted is the root of the binary search tree,rootpwill be adjusted. Thetwalk() function walks the binary search tree rooted inrootand calls the functionactionon each node. Theactionfunction is called with three arguments: a pointer to the current node, a value from the enumtypedefenum{preorder,postorder,endorder,leaf}VISIT;specify- ing the traversal type, and a node level (where level zero is the root of the tree).## RETURN VALUES

Thetsearch() function returns NULL if allocation of a new node fails (usually due to a lack of free memory). Thetfind(),tsearch(), andtdelete() functions return NULL ifrootpis NULL or the datum cannot be found. Thetwalk() function returns no value.## SEE ALSO

bsearch(3), hsearch(3), lsearch(3) DragonFly 3.5 June 15, 1997 DragonFly 3.5

Search: