Wir fangen nur nun von rechts an statt von links, da bei Post-Order die Wurzel ganz rechts ist
Lösung
Die letzte Zahl der Postorder ist immer die Wurzel des Baumes. Hier also:
Post-Order: 4,2,6,7,5,3,1
In der Inorder-Liste steht 1 an folgender Stelle:
In-Order: 4,2,1,6,5,7,3
Alles links von 1 gehört zum linken Teilbaum (4, 2).
Alles rechts von 1 gehört zum rechten Teilbaum (6, 5, 7, 3).
1 / \ {4,2} {6,5,7,3}
Die nächste Wurzel aus der Postorder ist 3:
Post-Order: 4,2,6,7,5,3,1
In der Inorder-Liste steht 3 hier:
In-Order: 4,2,1,6,5,7,3
Links von 3 steht (6, 5, 7), das der linke Teilbaum von 3 ist.
1 / \ . {4,2} 3 / {6,5,7}
Nun nehmen wir 5 aus der Postorder:
Post-Order: 4,2,6,7,5,3,1
In der Inorder-Liste steht 5 hier:
In-Order: 4,2,1,6,5,7,3
Links von 5 steht 6, das der linke Teilbaum von 5 ist.
Rechts von 5 steht 7, das der rechte Teilbaum von 5 ist.
1 / \ {4,2} 3 / 5 / \ 6 7
Als nächstes kommt 7:
Post-Order: 4,2,6,7,5,3,1
7 hat keine weiteren Kinder in der Inorder-Liste.
1 / \ {4,2} 3 / 5 / \ 6 7
Jetzt nehmen wir 6 aus der Postorder:
Post-Order: 4,2,6,7,5,3,1
6 hat keine weiteren Kinder, da es in der Inorder-Liste alleine steht.
1 / \ {4,2} 3 / 5 / \ 6 7
Zum Schluss verarbeiten wir den linken Teilbaum. Die nächste Zahl aus der Postorder ist 2:
Post-Order: 4,2,6,7,5,3,1
In der Inorder-Liste steht 2 hier:
In-Order: 4,2,1,6,5,7,3
Links von 2 steht 4, das der linke Teilbaum von 2 ist.
1 / \ 2 3 / / 4 5 / \ 6 7
Zum Schluss verarbeiten wir 4:
Post-Order: 4,2,6,7,5,3,1
4 hat keine weiteren Kinder.
1 / \ 2 3 / / 4 5 / \ 6 7
Fazit
Der rekonstruierte Baum sieht so aus:
1 / \ 2 3 / / 4 5 / \ 6 7
Zusatzfrage 3: Pre-Order und Post-Order
Achtung: Mehrdeutigkeit bei Preorder und Postorder
Die Rekonstruktion eines binären Baums nur anhand der Preorder- und Postorder-Traversierung ist nicht eindeutig. Beide Traversierungen liefern nicht genügend Informationen, um die Baumstruktur in allen Fällen klar zu definieren, insbesondere bei:
Knoten mit nur einem Kind (einseitige Bäume),
Situationen, in denen die Reihenfolge der Kinder unklar ist.
Das bedeutet, dass Preorder und Postorder zu mehreren möglichen Baumstrukturen führen können. Um einen binären Baum eindeutig zu rekonstruieren, ist die Inorder-Traversierung oder zusätzliche Informationen erforderlich.
Nicht eindeutig bestimmbar (damit du es mal gesehen hast)
Beispiel zur Mehrdeutigkeit von Preorder und Postorder
Nehmen wir an, wir haben die folgenden Arrays gegeben:
Das Element direkt nach der Wurzel in der Preorder-Liste ist immer das linke Kind der Wurzel. Hier ist 2 das linke Kind von 1.
Nun müssen wir den gesamten linken Teilbaum von 1 bestimmen. In der Postorder-Liste endet der linke Teilbaum immer direkt vor der Wurzel. Da 2 der Wurzel des linken Teilbaums ist, sind alle Elemente vor 2 in der Postorder-Liste Teil des linken Teilbaums:
Postorder: 8,9,4,5,2,6,7,3,1
Die Knoten {8, 9, 4, 5, 2} gehören also zum linken Teilbaum von 1, und {6, 7, 3} gehören zum rechten Teilbaum.
Der Baum sieht also nun folgendermaßen aus:
1 / \ {8, 9, 4, 5, 2} {6, 7, 3}
Schritt 3: Rekursion im linken Teilbaum
Wir wenden nun das gleiche Prinzip rekursiv auf den linken Teilbaum an. In der Preorder-Liste sehen wir, dass 2 die Wurzel dieses Teilbaums ist, und 4 ist das linke Kind von 2:
Preorder: 1,2,4,8,9,5,3,6,7
In der Postorder-Liste sehen wir, dass der Teilbaum von 2 mit 4 und 5 gefüllt ist:
Postorder: 8,9,4,5,2,6,7,3,1
Somit ist 4 das linke Kind von 2 und 5 das rechte Kind.
Schritt 4: Rekursion im Teilbaum von 4
8 und 9 sind die Kinder von 4, da sie in der Preorder-Liste direkt nach 4 folgen:
Durch diese rekursive Methode konnten wir den Baum korrekt aus den Preorder- und Postorder-Listen rekonstruieren. Allerdings funktioniert diese Methode nur, weil der Baum hier vollständig ist. In anderen Fällen, insbesondere bei Bäumen mit einseitigen Verzweigungen, könnte die Rekonstruktion mehrdeutig sein.
Extraressource für die Binärbaumkonstruktion falls immernoch unklar
c) Implementieren Sie rekursiv die drei Traversierungsmethoden. Das Bearbeiten eines Knotens soll dabei darin bestehen, dass sein Inhalt auf dem Bildschirm ausgegeben wird.
Lösung
1. Knotenklasse erstellen:
Die Node-Klasse dient als Grundstruktur für die Knoten im Binärbaum. Jeder Knoten hat drei Attribute:
value: der Wert des Knotens (in deinem Beispiel ein Buchstabe).
left: Verweis auf den linken Kindknoten.
right: Verweis auf den rechten Kindknoten.
// Node.javapublic class Node { String value; Node left; Node right; public Node(String value) { this.value = value; }}
Erstelle nun eine Klasse BinaryTreeSolution.java
public class BinaryTreeSolution {}
2. Daten für den Binärbaum hinzufügen:
Hier wird eine Funktion erstellt, die den Baum aufbaut, indem Knoten erstellt und miteinander verbunden werden. Diese Funktion gibt den Wurzelknoten (Knoten “a”) zurück.
Nun fügen wir Nutzdaten in unseren BinaryTree hinzu
Dafür sei für dieses Beispiel folgender Baum gegeben:
a / \ b g / \ c d / e \ f
Dies implementieren wir nun in unseren Code
public class BinaryTreeSolution {public static Node createData_alphabet() { Node a = new Node("a"); Node b = new Node("b"); Node c = new Node("c"); Node d = new Node("d"); Node e = new Node("e"); Node f = new Node("f"); Node g = new Node("g"); a.left = b; a.right = g; b.left = c; b.right = d; c.left = e; e.right = f; return a; }}
3. Traversiermethoden:
Beim Traversieren eines Binärbaums geht es darum, alle Knoten des Baumes in einer bestimmten Reihenfolge zu besuchen. Die drei gängigen Methoden sind Preorder, Inorder und Postorder.
a) Preorder-Traversierung:
Beim Preorder-Ansatz wird zuerst der aktuelle Knoten bearbeitet, danach der linke und schließlich der rechte Kindknoten.
public static void inorderTraversal(Node n) { if (n == null) { return; } inorderTraversal(n.left); // Traversiere den linken Teilbaum System.out.print(n.value + " "); // Verarbeite den Knoten inorderTraversal(n.right); // Traversiere den rechten Teilbaum}
Rekursion:
Die Traversiermethoden funktionieren rekursiv, was bedeutet, dass eine Funktion sich selbst aufruft, um das Problem zu lösen. In diesem Fall rufen die Traversierfunktionen sich selbst für den linken und rechten Teilbaum eines Knotens auf.
Beispiel Preorder:
Starte bei Knoten “a”.
Gib “a” aus.
Rekursiver Aufruf für den linken Teilbaum (Knoten “b”).
Gib “b” aus und rufe die Methode für den linken Teilbaum von “b” auf (Knoten “c”).
Dieser Prozess wiederholt sich für jeden Knoten.
Durch diese rekursive Struktur wird sichergestellt, dass alle Knoten in der richtigen Reihenfolge durchlaufen werden.
Unsere BinaryTreeSolution Klasse sieht also nun so aus:
public class BinaryTreeSolution {public static Node createData_alphabet() { Node a = new Node("a"); Node b = new Node("b"); Node c = new Node("c"); Node d = new Node("d"); Node e = new Node("e"); Node f = new Node("f"); Node g = new Node("g"); a.left = b; a.right = g; b.left = c; b.right = d; c.left = e; e.right = f; return a; }public static void preorderTraversal(Node n) { if (n == null) { return; } System.out.print(n.value + " "); preorderTraversal(n.left); preorderTraversal(n.right);}public static void postorderTraversal(Node n) { if (n == null) { return; } postorderTraversal(n.left); postorderTraversal(n.right); System.out.print(n.value + " ");}public static void inorderTraversal(Node n) { if (n == null) { return; } inorderTraversal(n.left); System.out.print(n.value + " "); inorderTraversal(n.right);}}
Um zu testen, ob sie auch gut funktioniert, fügen wir eine public static void main(String[] args) {} Methode hinzu
Was ist public static void main?
public static void main(String[] args) ist die zentrale Methode, mit der jedes Java-Programm startet. Sie ist sozusagen der “Startknopf” einer Java-Anwendung.
public: Diese Methode ist öffentlich und für andere Klassen zugänglich. Das bedeutet, dass sie von überall im Programm aufgerufen werden kann, was wichtig ist, da die Java Virtual Machine (JVM) sie aufrufen muss, um das Programm zu starten.
static: Diese Methode gehört zur Klasse selbst und nicht zu einem Objekt der Klasse. Das heißt, sie kann aufgerufen werden, ohne dass ein Objekt der Klasse erstellt wird. Da die JVM das Programm startet, bevor irgendwelche Objekte existieren, ist dies entscheidend.
void: Die Methode gibt keinen Wert zurück. Sie führt nur Aktionen aus, startet das Programm und muss nichts an die JVM zurückliefern.
main: Der Name dieser Methode ist “main” und wird von der JVM gesucht, um den Startpunkt des Programms zu finden. Ohne eine main-Methode kann ein Java-Programm nicht ausgeführt werden.
String[] args: Hiermit können Argumente von der Kommandozeile an das Programm übergeben werden. Zum Beispiel, wenn du ein Programm ausführst und Parameter wie Dateinamen oder Einstellungen übergeben möchtest, werden diese in diesem Array gespeichert.
Zusammengefasst: Die Methode public static void main(String[] args) ist der Codeabschnitt, der automatisch aufgerufen wird, wenn dein Java-Programm gestartet wird. Ohne sie würde das Programm nicht wissen, wo es beginnen soll.
public class BinaryTreeSolution { public static Node createData_alphabet() { Node a = new Node("a"); Node b = new Node("b"); Node c = new Node("c"); Node d = new Node("d"); Node e = new Node("e"); Node f = new Node("f"); Node g = new Node("g"); a.left = b; a.right = g; b.left = c; b.right = d; c.left = e; e.right = f; return a; } public static void preorderTraversal(Node n) { if (n == null) { return; } System.out.print(n.value + " "); preorderTraversal(n.left); preorderTraversal(n.right); } public static void postorderTraversal(Node n) { if (n == null) { return; } postorderTraversal(n.left); postorderTraversal(n.right); System.out.print(n.value + " "); } public static void inorderTraversal(Node n) { if (n == null) { return; } inorderTraversal(n.left); System.out.print(n.value + " "); inorderTraversal(n.right); } public static void main(String[] args) { Node data_alphabet = createData_alphabet(); preorderTraversal(data_alphabet); System.out.println(); postorderTraversal(data_alphabet); System.out.println(); inorderTraversal(data_alphabet); }}
Als Ausgabe in der Kommandozeile/Terminal erhalten wir
a b c e f d gf e c d b g ae f c b d a g
d) Gegeben ist die folgende Methode:
public void wasTueIch(BinaryTree<Integer> b) { Stack<BinaryTree<Integer>> stapel = new Stack<BinaryTree<Integer>>(); while (!stapel.isEmpty() || !b.isEmpty()) { if (!b.isEmpty()) { stapel.push(b); b = b.getLeftTree(); } else { b = stapel.top(); stapel.pop(); System.out.println(b.getContent()); b = b.getRightTree(); } }}
Aufgabenstellung
Analysieren Sie die Arbeitsweise der Methode wasTueich, indem Sie die Bele-
gungen des Stapels sowie die Ausgabe auf dem Bildschirm für den abgebildeten
Baum notieren. Erläutern Sie, was die Methode leistet.
public void wasTueIch(BinaryTree<Integer> b) { // Erstelle einen leeren Stapel zum Speichern der Knoten Stack<BinaryTree<Integer>> stapel = new Stack<BinaryTree<Integer>>(); // Solange entweder der Stapel nicht leer ist oder der aktuelle Baum nicht leer ist while (!stapel.isEmpty() || !b.isEmpty()) { if (!b.isEmpty()) { // Wenn der aktuelle Knoten existiert (nicht null ist) // - Füge ihn dem Stapel hinzu für späteren Zugriff stapel.push(b); // - Bewege dich zum linken Kindknoten b = b.getLeftTree(); } else { // Wenn der aktuelle Knoten null ist (kein linker Kindknoten mehr) // - Hole den obersten Knoten vom Stapel (zurück zum Elternknoten) b = stapel.top(); stapel.pop(); // - Gib den Inhalt des Knotens aus (Verarbeitung des Knotens) System.out.println(b.getContent()); // - Bewege dich zum rechten Kindknoten b = b.getRightTree(); } }}
Die Methode wasTueIch führt eine in-order Traversierung (symmetrischer Durchlauf) des binären Baums b durch und gibt die Inhalte der Knoten in dieser Reihenfolge auf dem Bildschirm aus.
Arbeitsweise der Methode:
Initialisierung:
Ein leerer Stapel stapel wird erstellt.
Die Methode beginnt mit dem übergebenen Baum b.
Schleife:
Die while-Schleife läuft, solange entweder der Stapel nicht leer ist oder der aktuelle Knoten b nicht leer ist.
Wenn b nicht leer ist:
Der aktuelle Knoten b wird auf den Stapel gelegt.
b wird auf seinen linken Kindknoten gesetzt (b = b.getLeftTree()).
Dies wiederholt sich, bis der linke äußerste Knoten erreicht ist.
Wenn b leer ist:
Der oberste Knoten wird vom Stapel genommen (stapel.pop()).
Der Inhalt dieses Knotens wird ausgegeben (System.out.println(b.getContent())).
b wird auf seinen rechten Kindknoten gesetzt (b = b.getRightTree()).
Erläuterung:
Die Methode traversiert den Baum so weit wie möglich nach links und speichert dabei die Knoten auf dem Stapel.
Wenn kein linker Knoten mehr vorhanden ist, wird der letzte gespeicherte Knoten vom Stapel genommen, sein Wert ausgegeben, und die Traversierung setzt sich mit seinem rechten Teilbaum fort.
Dieses Vorgehen führt dazu, dass die Knoten in der Reihenfolge “links - Wurzel - rechts” besucht werden.
Fazit:
Die Methode wasTueIch realisiert eine in-order Traversierung des binären Baums und gibt dabei die Inhalte der Knoten in aufsteigender Reihenfolge aus (sofern der Baum sortiert ist). Diese Traversierungsmethode wird häufig verwendet, um die Elemente eines binären Suchbaums sortiert auszugeben.
e) Entwickeln Sie eine Strategie für eine Methode, die die Anzahl aller Knoten eines binären Baums bestimmt, Implementieren Sie Ihre Methode.
public static int countNodes(Node n) { if (n == null) return 0; return 1 + countNodes(n.left) + countNodes(n.right);}
Tiefergehende Erklärung
Gedankenprozess zur Methode countNodes
Zielsetzung:
Wir möchten die Gesamtanzahl der Knoten in einem binären Baum ermitteln. Ein Knoten ist jedes Element im Baum, das Werte enthält und eventuell auf linke und rechte Kinder verweist.
Wahl der Strategie:
Eine rekursive Methode eignet sich gut für diese Aufgabe, da ein binärer Baum eine hierarchische Struktur hat, die sich gut in kleinere Teilbäume zerlegen lässt. Die Rekursion erlaubt es uns, den Baum systematisch zu durchlaufen, indem wir sowohl die linke als auch die rechte Teilbäume besuchen.
Implementierung der Methode:
Die Methode countNodes ist wie folgt implementiert:
public static int countNodes(Node n) { if (n == null) return 0; return 1 + countNodes(n.left) + countNodes(n.right);}
Hier ist die Schritt-für-Schritt-Erklärung:
Base Case (Abbruchbedingung):
if (n == null) return 0;
Wenn der aktuelle Knoten null ist, bedeutet das, dass wir einen leeren Baum oder einen Blattknoten ohne Kinder erreicht haben.
In diesem Fall gibt es keine Knoten in diesem Teilbaum, daher wird 0 zurückgegeben.
Wenn der Knoten nicht null ist, bedeutet das, dass wir einen gültigen Knoten haben.
Wir zählen diesen Knoten (deshalb 1).
Dann rufen wir countNodes rekursiv für den linken Kindknoten (n.left) und den rechten Kindknoten (n.right) auf.
Die rekursive Methode berechnet die Anzahl der Knoten in den linken und rechten Teilbäumen. Die Ergebnisse dieser Aufrufe werden addiert.
Schließlich wird 1 (für den aktuellen Knoten) zu der Summe der Knoten im linken und rechten Teilbaum hinzugefügt.
Rekursive Funktionsweise:
Beispielbaum:
1
/ \
2 3
/ \
4 5
Rekursive Aufrufe:
Die Methode wird für Knoten 1 aufgerufen. Hier wird gezählt: 1 + countNodes(2) + countNodes(3).
Für Knoten 2 wird gezählt: 1 + countNodes(4) + countNodes(5).
Knoten 4 und 5 sind Blätter (keine Kinder), daher geben die Aufrufe countNodes(null) für ihre Kinder 0 zurück.
Knoten 3 ist ebenfalls ein Blatt, also countNodes(null) für seine Kinder gibt 0 zurück.
Ergebnisse:
Knoten 4 und 5 liefern jeweils 1.
Knoten 2 zählt 1 + 1 + 1 = 3.
Knoten 3 zählt 1.
Knoten 1 zählt 1 + 3 + 1 = 5.
Zusammenfassung
Die Methode countNodes verwendet Rekursion, um durch den gesamten Baum zu traversieren und die Anzahl der Knoten zu zählen. Sie arbeitet nach dem Prinzip “Teile und herrsche”, indem sie den Baum in kleinere Teilbäume zerlegt und die Ergebnisse zusammenführt. Der Basisfall sorgt dafür, dass die Rekursion endet, wenn keine weiteren Knoten mehr vorhanden sind.