home  |  suche  |  kontakt/johner  |  institut 
studierende  |  tech-docs  |  mindmailer 

Bäume

Bäume stellen hierarchische Strukturen dar. In der Informatik werden Bäume als Datenstruktur eingesetzt. Oft wird zum Beispiel ein Organigramm, ein Familienstammbaum oder ein Mindmap ist einer Baumstruktur dargestellt.

Im Vergleich zu linearen Listen gibt es sowohl Gemeinsamkeiten als auch Unterschiede.

Gemeinsamkeit: - nur ein direkter Vorfahre

Unterschiede:    - Bäume können mehrere direkte Nachfolger haben

                          - in Bäumen gibt nie Zyklen

Ein Baum besteht aus verschiedenen Teilen und Merkmalen, außerdem unterscheidet man verschiedene Arten von Bäumen.

 Baummerkmale:

MerkmalBeschreibung
Grad eines KnotensAnzahl Kinder eines Knotens
Grad eines Baumsmaximaler Grad im Baum
Höhelängster vorkommender Pfad  (=größtes Niveau)
Niveaualle Knoten der gleichen Tiefe (beginnende mit Niveau = 0 an der Wurzel)
BlattKnoten ohne Nachfolger
Tiefe (eines Knotens)Abstand des Knotens bis zur Wurzel

 

Baumarten:

BaumartBeschreibung
BinärbaumGrad des Baumes ist 2
VielwegbaumGrad des Baumes ist >2
Binärer Suchbaumlinker Teil (Wert/Schlüssel) von einem Knoten ist kleiner als der Wert des Knotens selbst und der rechte Teil ist größer dem Knotenwert
Vollständiger Suchbaumauf jedem Niveau n<Höhe (letztes Niveau wird nicht beachtet) gibt es die maximale Knotenanzahl (max. Knotenanzahl entspricht der Zahl 2 hoch n)
Höhenbilanzierter Suchbaumwenn sich für jeden Knoten die Höhen seiner Teilbäume um höchstens 1 unterscheidet. (Anzahl Knoten des rechten Teilbaums - Anzahl Knoten des linken Teilbaums <= |1| ). Ein vollständiger Suchbaum ist immer auch höhenbilanziert, aber nicht umgekehrt! Somit ist die Vollständigkeit die höhere Forderung.
Voller Suchbaumauf jedem Niveau gibt es die maximal e Knotenanzahl

 

Anhand einiger Beispiele sollen die Begriffe  veranschaulicht werden.

Zeichnen Sie einen binären Suchbaumbaum, in den die Zahlen 6, 2, 9, 11, 5, 4, 3, 8, 10 eingefügt werden. Wie sieht der Baum aus, wenn es sich um einen höhenbilanzierten Baum handelt?

 

ACHTUNG: Fehler im obigen Bild: Die 8 hätte links von der 9, nicht links von der 11 einsortiert werden müssen! Entsprechend stünde die 10 links von der 11.

Folgendes Beispiel zeigt die Merkmale eines Baums. Dieser Baum ist höhenbilanziert aber nicht vollständig, weil es zum Beispiel auf dem Niveau 3 nur 5 Knoten gibt anstatt der erforderlichen 8 (2 hoch 3).

Um die Elemente in einem Baum zu durchlaufen gibt es verschiedene Verfahren. Bekannte Verfahren sind die pre-order, post-order und in-order. Wird ein Baum mit dem pre-order Verfahren durchlaufen wird jedes Element, beim erstenmal erreichen ausgegeben. Wir der obige Baum mit dem pre-order Verfahren durchlaufen, würde die Ausgabe folgendermaßen aussehen:

14-7-4-6-13-24-20-16-15-23-21-38-31-33-40

Das post-order Verfahren gibt die Elelemente erst beim letztmaligen Durchlaufen aus, dies würde folgendermaßen aussehen:

6-4-13-7-15-16-21-23-20-33-31-40-38-24-14

Bei einem in-order Verfahren wird das Element ausgegeben, sobald es zum zweiten mal durchlaufen wurde:

 6-4-7-13-14-15-16-20-21-23-24-33-31-38-40