Bäume als spezielle Art von Graphen

2.1 Hauptkomponenten eines Baumes

Ein Baum ist eine spezielle Art von Graph, der azyklisch und verbunden ist. In einem Baum gibt es einen einzigen Weg zwischen jedem Paar von Knoten, was seine Struktur hierarchisch macht.

Hauptkomponenten eines Baumes:

1. Knoten:

• Grundelemente des Baumes, die Daten enthalten.
• Zum Beispiel repräsentiert jeder Kreis im Diagramm einen Knoten.

2. Wurzel:

• Ein Knoten, der keine Elternknoten hat. Er ist der Ausgangspunkt des Baumes.
• Zum Beispiel der oberste Knoten im Diagramm.

3. Blätter:

• Knoten, die keine Kindknoten haben. Sie befinden sich an den "Enden" des Baumes.
• Zum Beispiel die Knoten am unteren Rand des Diagramms.

4. Kanten:

• Verbindungen zwischen den Knoten. Sie bestimmen die Eltern-Kind-Beziehungen zwischen den Knoten.
• Zum Beispiel die Linien, die die Knoten im Diagramm verbinden.

5. Teilbäume:

• Jedes Teilset des Baumes, bestehend aus einem Knoten und all seinen Nachkommen.
• Zum Beispiel ein Ast des Baumes, der von einem Knoten ausgeht.

Wichtige Merkmale eines Baumes:

1. Höhe des Baumes:

• Die Länge des Weges von der Wurzel bis zum entferntesten Blatt.
• Zum Beispiel die Anzahl der Ebenen im Diagramm.

2. Tiefe eines Knotens:

• Die Länge des Weges von der Wurzel bis zu diesem Knoten.
• Zum Beispiel die Anzahl der Ebenen von der Wurzel bis zu einem bestimmten Knoten.

2.2 Binärbäume

Es gibt verschiedene Arten von Bäumen. Fangen wir mit den einfachsten an.

Ein Binärbaum ist ein Baum, bei dem jeder Knoten höchstens zwei Kindknoten hat, die als linker und rechter Nachkomme bezeichnet werden.

Beispiel eines Binärbaums:

Besondere Arten von Binärbäumen:

Vollständiger Binärbaum:

Alle Ebenen des Baumes, außer der letzten, sind vollständig gefüllt, und alle Knoten der letzten Ebene sind so weit links wie möglich platziert.

Perfekter Binärbaum:

Alle inneren Knoten haben genau zwei Kindknoten, und alle Blätter befinden sich auf derselben Ebene.

Ausgewogener Binärbaum:

Der Höhenunterschied der Teilbäume eines beliebigen Knotens beträgt nicht mehr als 1.

Suchbaum:

Für einen beliebigen Knoten enthält sein linker Teilbaum nur Knoten mit kleineren Werten und sein rechter Teilbaum nur Knoten mit größeren Werten.

2.3 n-äre Bäume

Ein n-ärer Baum ist ein Baum, bei dem jeder Knoten höchstens n Kindknoten haben kann.

Besondere Arten von n-ären Bäumen:

1. Ternärer Baum (Ternary Tree):

Jeder Knoten hat höchstens drei Kindknoten.

2. K-ärer Baum (k-ary Tree):

Jeder Knoten hat höchstens k Kindknoten.

Beispiel eines 3-ären Baums (jeder Knoten hat höchstens drei Kindknoten):

2.4 Anwendungsbeispiele für Bäume

1. Dateisystem

Anwendung von Bäumen: Darstellung der hierarchischen Struktur von Dateien und Ordnern im Betriebssystem.

Der Wurzelknoten repräsentiert das Stammverzeichnis, innere Knoten — Ordner, und Blätter — Dateien. Operationen umfassen das Erstellen, Löschen und Verschieben von Dateien und Ordnern.

2. Entscheidungsbaum

Anwendung von Bäumen: Analytik und maschinelles Lernen zur Entscheidungsfindung.

Innere Knoten repräsentieren Fragen oder Bedingungen, Zweige — mögliche Antworten, und Blätter — endgültige Entscheidungen oder Aktionen. Beispielsweise die Diagnose von Krankheiten in der Medizin basierend auf Symptomen.

3. XML/HTML-Dokument

Anwendung von Bäumen: Strukturierte Darstellung von Daten im XML oder HTML-Format.

Der Wurzelknoten repräsentiert das gesamte Dokument, innere Knoten — Tags und Elemente, und Blätter — Textknoten und Attribute. Dies hilft beim Parsen und Manipulieren des Inhalts von Dokumenten.

4. Organisationsstruktur

Anwendung von Bäumen: Darstellung der Hierarchie in Organisationen und Unternehmen.

Der Wurzelknoten repräsentiert den Geschäftsführer, innere Knoten — Manager und Abteilungen, und Blätter — Mitarbeiter. Dies hilft, die organisatorische Struktur zu visualisieren und zu verwalten.

5. Schachspiel

Anwendung von Bäumen: Darstellung möglicher Züge im Spiel.

Der Wurzelknoten repräsentiert den Anfangszustand des Spiels, innere Knoten — mögliche Züge, und Blätter — Endzustände des Spiels. Dies hilft bei der Planung von Strategien und Entscheidungshilfen in Schachprogrammen.