Baumstrukturen
Grundlagen von Baumstrukturen
Baumstrukturen sind hierarchische Datenstrukturen, die in der Informatik weit verbreitet sind.
Grundbegriffe
- Knoten: Einzelne Elemente im Baum
- Wurzel: Der oberste Knoten des Baumes
- Blatt: Knoten ohne Kinder
- Vorgänger/Elternknoten: Übergeordneter Knoten
- Nachfolger/Kinderknoten: Untergeordnete Knoten
- Tiefe: Abstand von der Wurzel
- Höhe: Maximale Tiefe aller Knoten
Binärbäume
Ein Binärbaum ist ein Baum, bei dem jeder Knoten höchstens zwei Kinder hat:
- Linkes Kind
- Rechtes Kind
Eigenschaften
- Vollständiger Binärbaum: Alle Ebenen sind vollständig gefüllt
- Balancierter Baum: Höhenunterschiede zwischen Teilbäumen minimal
- Binärer Suchbaum: Geordnete Struktur für effiziente Suche
Anwendungen
- Suchbäume
- Entscheidungsbäume
- Dateisysteme
- Ausdruck-Evaluierung
- Huffman-Codierung
Traversierung
- Inorder: Links → Wurzel → Rechts
- Preorder: Wurzel → Links → Rechts
- Postorder: Links → Rechts → Wurzel
