Einleitung

ZURÜCK ---- INHALTSVERZEICHNIS ---- WEITER

Einsatz von Bäumen

Bäume sind eine wichtige Datenstruktur in der Informatik. Jeder rekursiver Datentyp, der eine nichtlineare Struktur aufweist, kann als Baum bezeichnet werden.
Bäume werden zur

eingesetzt.

Es gibt eine Menge verschiedener Abarten von Bäumen. Eine Klassifizierung von Bäumen kann anhand der Verzweigungsstruktur, der Sicherung der Daten im Baum und dem Verhältnis gesicherter Daten in verschiedenen Teilen des Baumes erfolgen.
Dieser Vortrag soll einige Basisarten von Bäumen aufzeigen und verschiedene Verarbeitungen und Eigenschaften dieser Bäume in Haskell zeigen. Dabei soll schon jetzt darauf hingewiesen sein, dass die folgenden Implementierungen auch auf andere Arten erfolgen können, diese hier gezeigte Art ist eine reine Beispielimplementierung.

 

Häufig genutzte Baumbegriffe

Wurzel
Die Wurzel des Baumes ist der Ausgangspunkt des Baumes, von hier ist der Zugriff auf jeden einzelnen Knoten möglich

Zweige, Äste, Kanten
Verzweigungen innnerhalb des Baumes

Blatt, Externer Knoten
Ist ein EndKnoten des Baumes, von hier gibt es keine weiteren Verzweigungen

Innerer Knoten
Knoten der kein Blatt ist sondern weiter verzweigt ist

Teilbaum
Ist ein Teil des gesamten Baumes, wobei ein Knoten mitsamt seiner Äste gewählt wird

 

Eigenschaften von Bäumen

Größe
Die Größe des Baumes wird je nach Baumart verschieden ausgelegt. Dies kann zum einen der Anzahl aller Knoten (Binäre Suchbüme), die Anzahl externer Knoten (Binäre Bäume) oder einer anderen Knotensummierung entsprechen.

Höhe
Die Höhe des Baumes ist die längste Verästelung innerhalb des Baumes von Wurzel bis zum Blatt.

Ausgewogenheit
Als einen ausgewogenen Baum bezeichnet man einen Baum dessen längster Weg von Wurzel bis zum Blatt (Höhe) nur um eins größer ist als der kürzeste Weg.

Perfekt
Ein Baum ist perfekt, wenn alle Verästelungen gleich lang/tief sind.

 

Baumdurchlaufarten

inorder
Auswertung des linken Teilbaums des Knotens k
Auswertung des Knotens k
Auswertung des rechten Teilbaums des Knotens k

Diese Art des Baumdurchlaufs wird zum Beispiel zur Ausgabe sortierter Bäume genutzt.

preorder
Auswertung des Knotens k
Auswertung des linken Teilbaums des Knotens k
Auswertung des rechten Teilbaums des Knotens k

Diese Art des Baumdurchlaufs wird zum Beispiel zum Suchen in sortierten Bäumen genutzt.

postorder
Auswertung des linken Teilbaums des Knotens k
Auswertung des rechten Teilbaums des Knotens k
Auswertung des Knotens k

Diese Art des Baumdurchlaufs wird zum Beispiel zur Auswertung von arithmetischen Ausdrücken genutzt.

 

ZURÜCK ---- INHALTSVERZEICHNIS ---- WEITER