Nicht Lineare Strukturen + Sortierung

Binärbaum

Ein Binärbaum ist eine abstrakte Datenstruktur, die aus einer endlichen Menge von Knoten besteht, die durch Kanten miteinander verbunden sind.
Jeder Knoten wird, mit Ausnahme der Wurzel, durch seinen Elternknoten referenziert. Umgekehrt referenziert jeder Knoten selbst maximal zwei weitere Knoten, die als Kindknoten bezeichnet werden. Daher kann jeder Knoten auf genau einem Weg durch Referenzen der Vaterknoten erreicht werfen.

Wurzel: Der erste Knoten eines Baumes, auf welchem der gesamte Baum aufgebaut ist.
Kanten: verbinden zwei Knoten miteinander.
Blatt: Knoten ohne Nachkommen.

Grad eines Knoten: Anzahl seiner Nachfolger. Der höchste Knotengrad entspricht dem Grad des Baumes.

Pfad: Ein Weg von der Wurzel zu einem Knoten über dazwischen liegende Knoten.
Tiefe eines Knotens: Anzahl der Kanten auf dem Pfad von der Wurzel zum Knoten. Die maximale Tiefe aller Knoten im Baum entspricht der Tiefe des Baumes.
Höhe eines Knotens: Anzahl der Kanten auf dem längsten Pfad vom Knoten zu einem beliebigen Blatt. Die Höhe der Wurzel entspricht der Baumhöhe.
Ebene eines Knotens: Alle Knoten mit gleichen Abstand zur Wurzel liegen in derselben Ebene.
Geschwisterknoten: Knoten, die den gleichen Vorgänger haben.
Teilbaum: Ausschnitt eines Baumes (Baum aus Knoten und seinen Nachfolgern)

Vollständiger Binärbaum: Jeder interne Knoten hat genau 2 Nachfolger.
Vollkommener Binärbaum: Alle Blätter haben die gleiche Tiefe.

Traversieren eines Binärbaumes:
Um den Inhalt aller Knoten eines Binärbaumes auszugeben müssen alle Knoten in gewisser Reihenfolge durchlaufen werden.
preorder: Wurzel | Linker Teilbaum | Rechter Teilbaum
inorder: Linker Teilbaum | Wurzel | Rechter Teilbaum
postorder: Linker Teilbaum | Rechter Teilbaum | Wurzel

Binärer Suchbaum

Ein Binärer Suchbaum ist ein sortierter Binarbaum. Alle Elemente im linken Teilbaum sind kleiner, alle Elemente im rechten Teilbaum größer als ihre Wurzel. Das bedeutet das eine Totalordnung entsprechend des Ordnungskriteriums vorlieg.

Binären Suchbaum erstellen: Sind Werte innerhalb einer Liste gespeichert, kann man mit ihnen einen Suchbaum erstellen. Das Element an Stelle 0 wird zur Wurzel. Die restlichen Elemente werden entsprechend ihres Werts nach und nach in den linken oder rechten Unterbaum als entsprechende Nachfolger an ihrer richtigen Position eingefügt. Durch die Insert-Operation können auch neue Zahlen nachträglich in den Binären Suchbaum eingefügt werden.

Operationen:
- init(): Erstellen eines leeren binären Suchbaums.
- insert(n): Das Element n wird in Form eines neuen Knotens entsprechend der Totalordnung in den rechten oder linken Teilbaum hinzugefügt.
- remove(n): Das Element n wird gelöscht.
- member(n): Sollte das Element n im Baum existent sein, wird der Wert TRUE zurückgeliefert, ansonsten FALSE.
- isEmpty(): Solange der binäre Suchbaum leer ist, wird der Wert True zugeliefert, ansonsten FALSE.

Member(n): Vergleiche n mit dem Wert des Wurzelknotens. Wenn n gleich dem Wert des Wurzelknotens ist, ist das Element vorhanden. Wenn n kleiner als der Wert des Wurzelknotens ist, suche rekursiv im linken Teilbaum. Wenn n größer als der Wert des Wurzelknotens ist, suche rekursiv im rechten Teilbaum. (Hierbei wird auf jeder neuen Ebene erneut nach größer/kleiner überprüft). Es endet wenn das Element gefunden wurde (True), oder keine passenden folgeknoten existieren. (False)

Löschen eines Knoten:
Suche den Knoten mit dem Wert n. Wenn der Knoten keine Kindknoten hat, lösche ihn einfach. Wenn der Knoten einen Kindknoten hat, ersetze den Knoten durch seinen Kindknoten. Hat ein Knoten zwei Nachfolger, kann dieser entweder durch den größten Nachfolger der linken Seite oder den kleinsten Nachfolger der rechten Seite ersetzt werden. Es ist anzustreben das der Baum auf beiden Seiten ähnlich groß bleibt.

Graphentheorie

Ein Graph ist ein abstraktes Modell, das aus Knoten und Kanten besteht. Die Kanten repräsentieren Beziehungen oder Verbindungen zwischen den Knoten.

Gerichteter Graph: Jede Kanten hat eine feste Richtung, die durch Pfeile angezeigt wird. Sind zwei Knoten in beide Richtungen verbunden, sind sie "stark verbunden".
Ungerichteter Graph: Die Kanten haben keine feste Richtung. Besteht eine Kante zwischen zwei Knoten, so sind diese "verbunden". Ein ungerichteter Graph lässt sich immer als gerichteter Graph darstellen (mit zwei Pfeilen).

Grad eines Knoten: Der Grad eines Knotens gibt an, wie viele Kanten von ihm ausgehen. Bei gerichteten Graphen unterscheidet man zwischen Eingangsgrad und Ausgangsgrad.
Markierte Graphen: In markierten Graphen haben die Kanten Gewichte (für z.B.: Kosten oder Entfernungen) Ist eine Kante nicht Markiert beträgt ihr Gewicht 1

Pfad: Ein Weg zwischen zwei Knoten über dazwischen liegende Knoten. Notation: Pfad A-D: (A,B)(B,C)(C,D).
Pfadlänge: Die Summe aller Kantengewichte, die der Pfad durchläuft.
Minimaler Pfad: Der Pfad mit den niedrigsten Gesamtkosten zwischen zwei Knoten.

Zyklus: Eine geschlossener Pfad bei dem der Start- und Endknoten identisch sind, somit eine Schleife.
Eulerscher Kreis: Ein Zyklus, der jeden Knoten genau einmal durchläuft. (nur möglich, bei max. zwei Knoten mit ungeraden Grad)
Eulerweg: Ein Pfad, der jeden Knoten genau einmal durchläuft. (nur möglich, bei max. zwei Knoten mit ungeraden Grad)

Zusammenhängender Graph: Zwischen allen Knoten existieren Pfade.
Kreisfreie Graphen: Ein Graph ist kreisfrei, wenn er keine Zyklen enthält.

Ein Graph lässt sich in einer Adjazenzmatrix (Spalte = von | Zeile = zu) und einer Adjazenzliste darstellen.

Dijkstra-Algorithmus

Der Dijkstra-Algorithmus ist ein Greedy-Algorithmus, der den kürzesten Pfad von einem Startknoten zu allen anderen Knoten in einem gewichteten Graphen berechnet.
Die Kantengewichte können positiv oder negativ sein, jedoch nicht gleichzeitig positiv und negativ.

Breitensuche

Um den Inhalt aller Knoten eines Graphen auszugeben zu können, müssen alle Knoten in gewisser Reihenfolge durchlaufen werden. Die Breitensuche ist neben der Tiefensuche eine Möglichkeit zur Traversierung.

Es werden 2 Listen benötigt (Erledigt und Folgende) sowie eine Variable aktuell. In Erledigt werden die bereits besuchten Knoten eingespeichert, um Endlosschleifen durch Zyklen zu verhindern.

Starten wir bei mit Knoten A, so sieht das Geschehen bei der nullten Iteration folgendermaßen aus:
aktuell = A
Erledigt = []
Folgende = []

In der ersten Iteration werden alle Nachbarn von aktuell in Folgende übernommen:
aktuell = A
Erledigt = []
Folgende = [E, B ,C]

In der nächsten Iteration ist A erledigt, das erste Element der Liste Folgende (E) wird zum aktuellen Element und aus Folgende entfernt. Alle neuen Nachbarn von E werden zu Folgende zugefügt:
aktuell = E
Erledigt = [A]
Folgende = [B ,C, F ]

In der nächsten Iteration wird E zu Erledigt hinzugefügt, und B zum neuen Element aktuell. Seine neuen Nachbarn werden wieder zu Folgende hinzugefügt:
aktuell = B
Erledigt = [A, E]
Folgende = [C, F ]

Folgt man den Schritten bis aktuell leer ist, bildet Erledigt eine Liste aller Knoten, die über einen möglichen Pfad mit A verbunden sind, hier:
aktuell = None
Erledigt = [A, E, B, C, F, D]
Folgende = []

Tiefensuche

Um den Inhalt aller Knoten eines Graphen auszugeben zu können, müssen alle Knoten in gewisser Reihenfolge durchlaufen werden. Die Tiefensuche ist neben der Breitensuche eine weitere Möglichkeit zur Traversierung.

Es wird ein Stack Status, sowie eine Liste Ausgabe benötigt. Besuchte Knoten werden zudem markiert, um Endlosschleifen durch Zyklen zu verhindern. Starten wir mit Knoten A, so sieht das Geschehen nach der ersten Iteration folgendermaßen aus:
Markiert: A
Status = [A]
Ausgabe = [A]

Nun wird überprüft, ob das oberste Element im Stack (A), einen möglichen unmarkierten Nachfolger hat, hier ist dies E:  
Markiert: A, E
Status = [A, E]
Ausgabe = [A, E]

Nun wird erneut überprüft, ob das oberste Element im Stack (E), einen möglichen unmarkierten Nachfolger hat, hier ist dies F.
Markiert: A, E, F
Status = [A, E, F]
Ausgabe = [A, E, F]

Dieser Schritt wird so oft wiederholt, bis das oberste Element keinen unmarkierten Nachfolger mehr besitzt:
Markiert = A, E, F, C, D
Status = [A, E, F, C, D]
Ausgabe = [A, E, F, C, D]

Ist dies der Fall wird so lange das oberste Element im Stack mit pop() entfernt, bis der Stack leer ist, oder das oberste Element einen unmarkierten Nachfolger besitzt:
Markiert = A, E, F, C, D
Status = [A, E, F]
Ausgabe = [A, E, F, C, D]

F besitzt einen neuen Nachfolger (B), daher wird dieser auf den Stack gelegt, markiert, und in die Ausgabe überführt:
Markiert = A, E, F, C, D, B
Status = [A, E, F, B]
Ausgabe = [A, E, F, C, D, B]

Nun wird erneut überprüft, ob das oberste Element im Stack (B), einen möglichen unmarkierten Nachfolger hat. Ist dies nicht der Fall wird so lange das oberste Element im Stack mit pop() entfernt, bis der Stack leer ist, oder das oberste Element einen unmarkierten Nachfolger besitzt. Ist dies der Fall wiederholt sich der zuvorige Schritt mit dem neuen Knoten.

In unseren Beispiel wird der Stack jedoch vollkommen geleert, da alle Knoten Markiert sind. Die Ausgabe enthält nun Alle Knoten des Graphen:
Markiert = A, E, F, C, D, B
Status = []
Ausgabe = [A, E, F, C, D, B]

YouTube

Google Sites

Report abuse