Feststellen, ob ein Baum ein Suchbaum (geordneter Binärbaum) ist

Zunächst müssen Minimum und Maximum zurückgegeben werden können. Dafür benötigt es zwei Funktionen. Wenn der Baum leer ist, gibt es sowas nicht und damit eine violation. Wenn der passende Teilbaum leer ist, dann ist das Minimum/Maximum der Eintrag am Knoten. Wenn nicht, dann ruft sich die Funktion selbst wieder auf mit dem passenden Teilbaum.

Die eigentliche Funktion gibt einen booleschen Wert zurück. Wenn der Baum leer ist, dann true. Wenn beide Teilbäume leer sind, dann auch. Wenn nur einer der Teilbäume leer ist (hierfür 2 cond-Verzweigungen), dann muss das Wurzelelement größer bzw kleiner sein als das Minimum bzw Maximum des Teilbaumes und die Funktion muss für den Teilbaum erneut aufgerufen werden (dass alles mit and verknüpft). Wenn keiner der Teilbäume leer ist, müssen 4 Voraussetzungen erfüllt sein, die durch and verknüpft sind und aus der Kumulation dessen bestehen, was oben steht.


Keine Kommentare:

Kommentar veröffentlichen