Vorlesung Informatik 2 - Teil B: Theorie
4.1 Grundbegriffe zu Bäumen
Bäume gehören in der Praxis zu den häufigsten Datenstrukturen.
Beispiele für die Anwendung von Bäumen:
- Verzeichnisstruktur von Dateisystemen
- Hierarchie der Java Klassen
- Huffman Code
- Führungsstruktur einer Organisation
- Stammbäume sind im mathematischen Sinne keine Bäume - das liegt an der menschlichen Natur ("Your father ain't your fater but your father don't know)
Sie bestehen aus Knoten (node) und gerichteten Kanten (vertex).
Die wichtigsten Eigenschaften von Bäumen:
- die Knoten sind hierarchich angeordet, der oberste Knoten heißt Wurzel (root),
- alle Knoten außer der Wurzel haben eine Vater,
- ein Knoten kann ein oder mehrere Kinder (child) haben,
- eine Kante hat eine Richtung, sie zeigt vom Vater zu den Kindern
- ein Knoten ohne Kinder heißt Blatt (leaf)
- ein Knoten mit Vater und mindestens einem Kind heißt innerer Knoten (inner node)
- Geschwister-Knoten (sibling nodes), haben den gleichen Vater und sind auf der gleichen Ebene (level)
- ein Pfad (path) ist eine Folge von Knoten, und Kanten, es gibt keinen zyklischen Pfad
- ein absoluter Pfad (absolute path) beinnt mit der Wurzel
- die Pfadlänge (path length) ist die Anzahl der Knoten im Pfad
- B ist Nachkomme (descendant) von A wenn es einen Pfad von A nach B
- die Nachkommen eines Knotens K bilden eine Unterbaum (subtree) mit der Wurzel K
- die Tiefe (depth) eines Knotens ist die Länge seines absoluten Pfades (die Wurzel hat die Tiefe 1)
- die Höhe (height) eines Baums ist die maximale Tiefe seiner Knoten.
- ein Baum mit N Knoten hate N-1 Kanten
Bäume sind rekursiv:
Ein Baum ist leer oder besteht aus einer Wurzel und einer Liste von Teilbäumen.