Bäume

Bäume sind verallgemeinerte Listenstrukturen. Statt nur einen Nachfolger haben die Knoten mehrere Nachfolger, sogenannte Söhne. Dabei bestimmt die Ordnung die maximale Anzahl der Söhne. Bäume der Ordnung $d > 2$ nennt man Vielwegbäume, solche der Ordnung $d = 2$ Binärbäume. Knoten, die keine Söhne haben, werden als Blätter bezeichnet; alle anderen Knoten nennt man innere Knoten. Wir werden uns in den nächsten Beispielen mit Binärbäumen beschäftigen. Dazu gehören auch elementare Operationen wie Einfügen, Entfernen, ... eines Knotens.