tsearch, tfind, tdelete, twalk - binäre Suchbäume bearbeiten

Definition	#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));
Beschreibung	tsearch(), tfind(), tdelete() und twalk() manipulieren binäre Suchbäume. Vergleiche werden durch eine vom Benutzer gelieferte Funktion compar ausgeführt. Diese Funktion wird mit zwei Argumenten aufgerufen, d.h. mit den Zeigern auf die Elemente, die verglichen werden. Sie gibt eine ganze Zahl zurück, die kleiner, gleich oder größer als 0 ist, je nachdem, ob das erste Argument kleiner, gleich oder größer als das zweite Argument ist. Die Vergleichsfunktion braucht nicht jedes Byte zu vergleichen, und daher können außer den Werten, die verglichen werden, auch willkürliche Daten in den Elementen enthalten sein. tsearch() wird zum Aufbau des Baums und für den Zugriff auf den Baum verwendet. key ist ein Zeiger auf einen Wert, auf den zugegriffen bzw. der gespeichert werden soll. Wenn der Baum einen Wert aufweist, der gleich *key (der Wert, auf den der Schlüssel zeigt) ist, wird ein Zeiger auf diesen gefundenen Wert zurückgegeben. Andernfalls wird *key eingefügt und ein auf diesen key weisender Zeiger zurückgegeben. Es werden nur Zeiger kopiert, und daher müssen die Daten von der aufrufende Routine gespeichert werden. rootp zeigt auf eine Variable, die auf die Wurzel des Baums zeigt. Ein NULL-Wert für die Variable, auf die rootp zeigt, gibt einen leeren Baum an; in diesem Fall wird die Variable so gesetzt, dass sie auf den Wert zeigt, der sich an der Wurzel des neuen Baums befindet. Wie tsearch() sucht auch tfind() nach einem Wert im Baum und gibt einen Zeiger auf diesen Wert zurück, falls dieser gefunden wird. Wird der Wert nicht gefunden, gibt tfind() einen Nullzeiger zurück. Die Argumente für tfind() sind dieselben wie für tsearch(). Mit tdelete() wird ein Knoten in einem binären Suchbaum gelöscht. Die Argumente sind dieselben wie für tsearch(). Die Variable, auf die rootp zeigt, ändert sich, wenn der gelöschte Knoten die Wurzel des Baums war. tdelete() gibt einen Zeiger auf den Vaterknoten des gelöschten Knotens zurück oder einen Nullzeiger, wenn der Knoten nicht gefunden wurde. twalk() durchläuft einen binären Suchbaum. root ist die Wurzel des Baums, der durchlaufen werden soll. Jeder Knotenpunkt im Baum kann als Wurzel für ein Durchlaufen des Baums unterhalb dieses Knotens verwendet werden. action ist der Name einer Funktion, die an jedem Knoten aufgerufen werden soll. Diese Funktion wird mit drei Argumenten aufgerufen. Das erste Argument ist die Adresse des besuchten Knotens. Die Struktur, auf die dieses Argument zeigt, ist nicht spezifiziert und darf nicht verändert werden. Der Wert vom Typ ’Zeiger-auf-Knoten’ kann jedoch in den Typ ’Zeiger-auf-Zeiger-auf-Element’ konvertiert werden, um auf die in dem Knoten gespeicherten Elemente zugreifen zu können. Das zweite Argument ist ein Wert des Aufzählungstyps typedef enum { preorder, postorder, endorder, leaf } VISIT; (definiert in der Include-Datei search.h), abhängig davon, ob es sich um den ersten, zweiten oder dritten Besuch des Knotens handelt, bei einem Durchlauf des Baums in die Tiefe, von links nach rechts, oder ob der Knoten ein Blatt ist. Das dritte Argument stellt die Stufe des Knotens im Baum dar, wobei die Wurzel die Stufe Null ist.
Returnwert	Zeiger auf den gefundenen Knoten
		tsearch() und tfind(), wenn *key gefunden wurde.
	Zeiger auf die eingefügte  Position
		tsearch(), wenn *key nicht gefunden wurde, aber eingefügt werden konnte.
	Nullzeiger	tsearch(), wenn nicht ausreichend Speicher zur Erstellung eines neuen Knotens zur Verfügung steht. tsearch(), tfind() und tdelete(), wenn rootp zu Beginn NULL ist. tfind(), wenn *key nicht gefunden wurde.
	Zeiger auf den Vaterknoten des gelöschten Knotens
		tdelete() bei Erfolg.
Hinweise	root für twalk() ist um eine Stufe der indirekten Adressierung niedriger als rootp für tsearch() und tdelete(). Es gibt zwei Nomenklaturen für die Reihenfolge, in der die Knoten eines Baums durchlaufen werden. tsearch() verwendet die Begriffe "preorder", "postorder" und "endorder", um auszudrücken, dass ein Knoten vor seinen Söhnen oder nach dem linken und vor dem rechten Kind oder nach seinen Söhnen besucht wird. Die andere Nomenklatur verwendet "preorder", "inorder" und "postorder", um diese Reihenfolgen zu bezeichnen, wobei "postorder" eine andere Bedeutung hat. Wenn die aufrufende Funktion den Zeiger auf die Wurzel ändert, werden die Ergebnisse unvorhersagbar.
Siehe auch	bsearch(), hsearch(), lsearch(), search.h.