32561: Erstellung und Traversierung von/in Binärbäumen
Erstellen von Binärbäumen aus Bäumen der Ordnung 
Leider habe ich meine Bachelor-Unterlagen verlegt und musste mich für die Klausur für das Thema durch das Skript wühlen. Die Anleitung zur Baumtransformation beschränkt sich hier auf zwei richtige Sätze:
- R1: Söhne von Knoten sind linke Nachfolger
- R2: Brüder von Knoten sind rechte Nachfolger
Soweit so korrekt. Für mich war es jedoch noch nicht greifbar und auch das Bild half mir nicht besonders weiter. Liegt aber wohl eher an meinem deliriumartigen Zustand durch den massiven Missbrauch von alkoholfreiem Hustensaft. Zufällig habe ich ein Beispiel gefunden, dass mir jedoch auf die Sprünge half. Vielleicht hilft es euch auch:
Beispiel: Baumtransformation zum Binärbaum
Ein Binärbaum ist ein Baum, dessen Knoten höchstens zwei direkte Nachkommen haben. D. h. wir müssen den Baum so transformieren, dass seine logische Struktur zwar erhalten bleibt, aber der neue Baum diesem Kriterium entspricht.
Schritt 1:
Wenden wir jetzt die zwei Regeln R1 und R2 von oben auf die ersten zwei Zeilen mit Knoten A, B, C und D an. A hat als Söhne B, C und D. Es wird immer zuerst der erste Sohn von links genommen. Dieser wird Nachfolger von A (Anwendung R1, Pfeil zw. A und B). Nun wenden wir R2 auf Knoten B an: seine Brüder werden seine rechten Nachfolger (Anwendung R2, Pfeile von B zu C und von C zu D). So sieht unser Baum nach dem 1. Schritt aus.
Schritt 2:
Das gleiche machen wir nun jetzt mit der nächsten Zeile und Knoten E. Er ist erstes Kind von B und wird sein linker Nachfolger (R1). Knoten E hat einen Bruder und das wird sein rechter Nachfolger (R2).
Schritt 3:
Ab zum rechten Teil des Baumes. Knoten G ist erstes Kind von D und wird sein linker Nachfolger (R1). Knoten G hat zwei Brüder, die seine rechten Nachfolger werden (R2).
Schritt 4:
Bleiben die letzten zwei Knoten. J ist erster Sohn von H und wird sein linker Nachfolger (R1) und hat einen Bruder K, der sein rechter Nachfolger wird (R2).
Das ist der finale Baum.
Meiner Meinung nach ist die größte Denkblockade die Anwendung von R2. Denn "Brüder werden rechte Nachfolger" ist einfach gesagt, aber wenn der Knoten zwei Brüder hat, wer genau wird Nachfolger und wie sieht der Baum aus?
Hier sollte man einfach die Brüder auf einer Ebene belassen (siehe G, H und I) und sie einfach mit Pfeilen nach rechts verbinden. Den Teilbaum ist der nächsten Ebene (J und K) lässt man zunächst wie er ist, um ihn im nächsten Schritt dann bearbeiten zu können. Das hilft ungemein, wenn man unter Zeitdruck Bäume malen muss.
Traversierung
Im Rahmen meiner Vorbereitungen auf die Klausur bin ich mangels Übungen zu Binärbäumen und Traversierung in Pre-, Post- und InOrder auf folgende Seite, die ich euch nicht vorenthalten möchte. Tolle Übungsmöglichkeiten:
http://www.eex-online.de/informatik/binaerbaum.html
