Index

Datentypen (11)


Zeiger-Typ

3. Bäume

Bei zweifach verketteten Listen wurden bei einem Listenelement zwei Zeiger eingeführt. Der eine zeigte auf den Nachfolger, der andere auf den Vorgänger. Auch bei Bäumen werden mehrere Zeiger verwendet. Allerdings zeigen diese auf unterschiedliche Nachfolger. Es können hiermit beliebige Verzweigungen erreicht werden, so dass eine Baumstruktur entsteht.
Den Anfangszeiger bezeichnet man deswegen auch als Wurzel des Baumes. Die Elemente, deren Nachfolger-Zeiger auf mindestens ein weiteres Element zeigen, nennt man Knoten. Diejenigen Elemente bei denen kein Nachfolger-Zeiger auf ein weiteres Element zeigt, heißen auch Blätter. Alle Nachfolger-Zeiger der Blätter enthalten daher den Wert nil. Die Anzahl der Elemente der längsten Zeigerkette bezeichnet man als Höhe oder Tiefe des Baumes.

Baumstruktur

Bei Bäumen zeigen keine zwei Nachfolgerzeiger auf dasselbe Element. Strukturen, die das erlauben heißen allgemein Graphen. Die Bäume sind davon eine Teilmenge.

Wie bei den Listen, können auch Bäume eine doppelt verkettete Struktur aufweisen, indem jedem Element ein Vorgängerzeiger hinzugefügt wird. Dies erleichtert das Durchlaufen (Traversieren) von Bäumen.

Binärbäume

 

[Index] [Zurück/Listen] [Fortsetzung/Objekte]


Autor: Jürgen Dehmer
Letzte Änderung: 17. Februar 2001