Please enable JavaScript.
Coggle requires JavaScript to display documents.
nicht-lineare Datenstrukturen - Coggle Diagram
nicht-lineare Datenstrukturen
Binärbäume
pro Knoten höchstens zwei Nachkommen
Traversierungen
Ausgabe von Bäumen als Text

Pre-order
In-order
Post-order
Rekursion
Bestandteile
Abbruchbedingung
Reduktion des Problems
mind. 1 rekursiver Aufruf
Bäume können in einzelne Teilbäume aufgeteilt werden
binärer Suchbaum
Elemente müssen vergleichbar sein
Elemente im linken Teilbaum kleiner als Wurzel
Elemente im rechten Teilbaum größer als Wurzel
Algorithmus zum Einfügen über Insert-Methode in BinarySearchTree-Klasse
Implementierung
Graphen
Graph durchsuchen: Traveling Salesman Problem
Tiefensuche
Backtracking (Trial-n-Error)
Nicht zurückgehen, sondern so lange weitergehen, bis man nicht mehr weiterkommt. Wenn man nicht mehr weiterkommt, geht man eine Stufe zurück.
einfacher zu implementieren
lange Laufzeit bei größeren Graphen
Breitensuche
Dijkstra-Algorithmus
Schichtenweise absuchen: Immer alle Nachbarn in eine Schlange einordnen und schrittweise abarbeiten
extra Datenstruktur muss angelegt werden
sucht erst in der Umgebung des Startknotens
Arten von Graphen
gerichtete
ungerichtete
gewichtete
Darstellung
Adjazenzmatrix

Adjazenzliste


Implementierung
Bezeichnungen
Inhalte des Baums: Knoten
erster Knoten: Wurzel
Knoten ohne Nachkommen: Blätter
Verbindungen: Kanten
Ebenen
Pfad
Grad eines Knoten