Junior
Was ist ein binärer Baum?
sobes.tech KI
Antwort von AI
Ein binärer Baum ist eine Baumstruktur, bei der jeder Knoten höchstens zwei Nachkommen hat: links und rechts.
Hauptmerkmale:
- Wurzel (Root): Der oberste Knoten des Baumes.
- Knoten (Node): Element des Baumes, das Daten und Verbindungen zu seinen Nachkommen enthält.
- Kind (Child): Knoten, der direkt unter einem anderen Knoten (Elternteil) steht.
- Elternteil (Parent): Knoten, der direkt unter sich ein oder mehrere Nachkommen hat.
- Blatt (Leaf): Knoten ohne Nachkommen.
- Zweig (Branch): Pfad von der Wurzel bis zum Blatt.
- Teilbaum (Subtree): Baum, der aus einem Knoten und allen seinen Nachkommen besteht.
Verschiedene Arten von binären Bäumen:
- Vollständiger binärer Baum (Full Binary Tree): Jeder Knoten hat entweder 0 oder 2 Nachkommen.
- Perfekter binärer Baum (Perfect Binary Tree): Alle Ebenen außer der letzten sind vollständig gefüllt, und auf der letzten Ebene sind alle Knoten so weit links wie möglich angeordnet.
- Ausbalancierter binärer Baum (Balanced Binary Tree): Die Höhe der linken und rechten Teilbäume eines Knotens unterscheidet sich höchstens um 1. Beispiel: AVL-Baum, Rot-Schwarz-Baum.
- Degenerierter binärer Baum (Degenerate Binary Tree): Jeder Knoten hat höchstens einen Nachkommen. Im Wesentlichen ist dies eine verkettete Liste.
Wird in verschiedenen Algorithmen und Datenstrukturen verwendet, wie z.B. binäre Suchbäume, Heaps, Syntaxbäume.