1
Welt 1, Stammbaum
Baumstrukturen, Wurzel, Blatt, innere Knoten, Tiefe, Grad und Pfade.
Eine einzelne HTML Datei mit Übersichtsseite und eigenen Erklärseiten für alle sieben Welten. Jede Welt erklärt die wichtigsten Ideen mit großen, lesbaren Zeichnungen, Beispielen und kleinen interaktiven Elementen. Welt 2 enthält wieder eine richtige Schritt Animation für Preorder, Inorder und Postorder.
Baumstrukturen, Wurzel, Blatt, innere Knoten, Tiefe, Grad und Pfade.
Binärbaum, Morsecode, BinaryTree und ausführlich Preorder, Inorder, Postorder.
Binärer Suchbaum, suchen, einfügen, entfernen und entartete Bäume.
Graphen, Knoten, Kanten, Nachbarn, Gewichte und gerichtete Verbindungen.
Adjazenzmatrix und Adjazenzliste, zwei Arten Graphen zu speichern.
Tiefensuche, Breitensuche, Backtracking, Stack und Queue.
Dijkstra, kürzeste Wege, Distanz Tabelle und Vorgänger.
Ein Baum ist eine nicht lineare Datenstruktur. Das bedeutet: Die Elemente stehen nicht einfach hintereinander wie in einer Liste. Stattdessen gibt es Verzweigungen. Genau deshalb eignen sich Bäume für Hierarchien, Dateisysteme, Stammbäume oder Entscheidungswege.
Ein Baum besteht aus Knoten und Kanten. Ein Knoten speichert einen Inhalt. Eine Kante verbindet zwei Knoten. Ganz oben steht die Wurzel. Von dort aus verzweigt sich der Baum nach unten.
Der einzige Knoten ohne Vorgänger. Hier beginnt der Baum.
Ein Knoten mit mindestens einem Nachfolger.
Ein Knoten ohne Nachfolger. Hier endet ein Ast.
Die Tiefe eines Knotens zählt, wie viele Kanten man von der Wurzel bis zu diesem Knoten entlanggeht. Die Wurzel hat Tiefe 0. Die Höhe des Baums ist die größte vorkommende Tiefe.
Der Grad eines Knotens ist die Anzahl seiner direkten Nachfolger. Der Grad des gesamten Baums ist der größte Knotengrad im Baum.
Ein Pfad ist eine Folge von Knoten, die über Kanten verbunden sind. In einem Baum gibt es zwischen zwei Knoten genau einen eindeutigen Pfad. Dadurch ist immer klar, wie man von der Wurzel zu einem bestimmten Blatt kommt.
Diese Welt ist besonders wichtig: Ein Binärbaum ist ein Baum mit höchstens zwei Nachfolgern pro Knoten. Das passt perfekt zu Entscheidungen mit zwei Möglichkeiten, zum Beispiel kurz oder lang beim Morsecode. Außerdem geht es um die Frage, in welcher Reihenfolge man einen Baum besucht.
Ein Binärbaum besteht aus einer Wurzel, einem linken Teilbaum und einem rechten Teilbaum. Jeder dieser Teilbäume ist wieder ein Binärbaum. Auch ein leerer Teilbaum zählt als Teilbaum.
Alles, was links an einem Knoten hängt.
Alles, was rechts an einem Knoten hängt.
Ein Knoten kann 0, 1 oder 2 direkte Kinder haben.
Beim Morsecode entscheidet jedes Zeichen über die nächste Richtung. Ein kurzer Ton bedeutet links. Ein langer Ton bedeutet rechts. Am Ende der Zeichenfolge steht der gesuchte Buchstabe im erreichten Knoten.
Beispiel: kurz lang kurz führt zu R.
Gib einen Code mit Punkten und Strichen ein. Mehrere Buchstaben trennst du mit Leerzeichen. Beispiel: .- - .-. ergibt ATR.
Bei einem Baum gibt es keine einzige natürliche Reihenfolge wie bei einer Liste. Deshalb legt man eine Strategie fest. Die drei klassischen Strategien unterscheiden sich nur darin, wann die Wurzel bearbeitet wird.
Wurzel zuerst, danach linker Teilbaum, danach rechter Teilbaum. Die Wurzel kommt also ganz früh.
Erst linker Teilbaum, dann Wurzel, dann rechter Teilbaum. Die Wurzel liegt dazwischen.
Erst linker Teilbaum, dann rechter Teilbaum, danach die Wurzel. Die Wurzel kommt zuletzt.
Die Verfahren sind rekursiv. Man macht auf dem linken Teilbaum wieder dasselbe, danach auf dem rechten Teilbaum. Der einzige Unterschied ist die Position von besuche(Wurzel).
Die Animation hebt die Knoten genau in der Reihenfolge hervor, in der sie besucht werden. Die Buchstaben sind größer als vorher und bleiben gut lesbar.
In Java wird so ein Baum häufig als Objekt modelliert. Ein BinaryTree speichert einen Inhalt und zwei weitere BinaryTree Objekte als linken und rechten Teilbaum.
Ein binärer Suchbaum ist ein Binärbaum mit einer Zusatzregel: Links stehen kleinere Werte, rechts stehen größere Werte. Dadurch kann man beim Suchen große Teile des Baums überspringen.
Für jeden Knoten gilt: Alle Werte im linken Teilbaum sind kleiner. Alle Werte im rechten Teilbaum sind größer. Diese Regel muss an jeder Stelle im Baum stimmen, nicht nur an der Wurzel.
Bei jeder Station wird verglichen. Ist der gesuchte Wert kleiner, geht es links weiter. Ist er größer, geht es rechts weiter. Ist er gleich, ist die Suche fertig.
Einfügen funktioniert fast genauso wie Suchen. Man wandert mit Vergleichen nach links oder rechts, bis die passende freie Stelle erreicht ist. Dort wird der neue Knoten angehängt.
Ein Blatt kann einfach gelöscht werden.
Das Kind nimmt die Stelle des gelöschten Knotens ein.
Man ersetzt den Knoten meist durch den kleinsten Wert aus dem rechten Teilbaum.
Suche nach 60: 60 ist größer als 50, also rechts. 60 ist kleiner als 70, also links. Dann ist 60 gefunden.
Wenn Werte ungünstig eingefügt werden, zum Beispiel 10, 20, 30, 40, 50, entsteht fast eine Liste. Dann verliert der Suchbaum seinen Vorteil.
Ein Graph besteht aus Knoten und Kanten. Anders als ein Baum darf ein Graph Kreise enthalten. Außerdem kann es mehrere Wege zwischen zwei Knoten geben. Deshalb passen Graphen gut zu Stadtplänen, sozialen Netzwerken, Stromnetzen oder Webseiten.
Die Verbindung gilt in beide Richtungen. Eine Straße ohne Einbahnregel ist ein gutes Beispiel.
Die Verbindung hat eine Richtung. Eine Einbahnstraße oder ein Link auf einer Webseite ist ein Beispiel.
Ein Weg ist eine Folge von Knoten, die über Kanten verbunden sind. Ein Kreis ist ein Weg, der wieder beim Start landet. Ein Eulerweg benutzt jede Kante genau einmal. Ein Eulerkreis ist ein Eulerweg, der wieder am Start endet.
Von A nach F gibt es mehrere Wege, zum Beispiel A, C, E, F oder A, B, D, F. Genau das unterscheidet den Graphen vom Baum.
Ein Graph sieht als Bild leicht verständlich aus. Ein Computer braucht aber eine Speicherform. Die beiden typischen Varianten sind Adjazenzmatrix und Adjazenzliste.
Eine Adjazenzmatrix ist eine Tabelle. Zeilen und Spalten stehen für Knoten. In einer Zelle steht, ob es eine Kante gibt. Bei gewichteten Graphen steht dort das Gewicht.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 2 | 4 | 0 | 0 |
| B | 2 | 0 | 1 | 7 | 0 |
| C | 4 | 1 | 0 | 3 | 5 |
| D | 0 | 7 | 3 | 0 | 2 |
| E | 0 | 0 | 5 | 2 | 0 |
Eine Adjazenzliste speichert zu jedem Knoten nur die direkten Nachbarn. Bei gewichteten Graphen notiert man den Nachbarn zusammen mit dem Gewicht.
Viele Kanten, viele direkte Abfragen, kleine bis mittlere Knotenzahl.
Wenige Kanten, große Graphen, Speicherplatz ist wichtig.
Bei Graphen möchte man oft wissen, welche Knoten erreichbar sind oder wie man einen Weg findet. Dafür gibt es Suchverfahren. Die Tiefensuche geht zuerst tief in einen Weg hinein. Die Breitensuche betrachtet zuerst alle nahen Knoten.
DFS steht für Depth First Search. Die Suche geht so weit wie möglich in die Tiefe. Wenn es nicht weitergeht, läuft sie zurück. Dieses Zurücklaufen heißt Backtracking.
BFS steht für Breadth First Search. Die Suche besucht zuerst alle Knoten mit Abstand 1 vom Start, danach alle mit Abstand 2 und so weiter.
Starte eine Suche bei A. DFS und BFS besuchen denselben Graphen in unterschiedlicher Reihenfolge.
A, B, D, G, E, C, F
A, B, C, D, E, F, G
Dijkstra berechnet kürzeste Wege in einem gewichteten Graphen mit nicht negativen Kantengewichten. Er merkt sich für jeden Knoten die bisher beste bekannte Distanz und verbessert diese Schritt für Schritt.
Die Animation zeigt, welcher Knoten als Nächstes fest wird und wie sich die Distanzen ändern.
| Knoten | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| Distanz | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| Vorgänger | - | - | - | - | - | - |
In diesem Beispiel ist der kürzeste Weg von A nach F: A, C, B, D, F mit Gesamtkosten 11.