Was ist ein binärer Baum?

Ein binärer Baum ist eine Datenstruktur in Baumform, bei der jeder Knoten höchstens zwei Kindknoten hat: links und rechts.

Wichtige Merkmale:

• Jeder Knoten hat einen Zeiger auf seinen Wert (Daten) und Zeiger auf seine linken und rechten Kindknoten (können leer sein).
• Es gibt einen Wurzelknoten, der oberste Knoten des Baumes, ohne Vorfahren.
• Blätter sind Knoten ohne Kinder.
• Teilbäume sind jeder der binären Bäume, die den Wurzelbaum bilden.

Haupttypen binärer Bäume:

• Vollständiger binärer Baum: Auf jeder Ebene, außer möglicherweise der letzten, haben alle Knoten zwei Kindknoten, und auf der letzten Ebene sind alle Knoten nach links verschoben.
• Perfekter binärer Baum: Alle Ebenen sind vollständig gefüllt, und jeder Knoten (außer Blätter) hat zwei Kindknoten.
• Ausbalancierter binärer Baum: Die Höhen der linken und rechten Teilbäume jedes Knotens unterscheiden sich höchstens um 1.

Anwendungen in QA:

• Testhierarchie: Organisation von Testszenarien oder Testsets in einer Baumstruktur für bessere Lesbarkeit und Navigation.
• Suche und Sortierung von Daten: Binäre Suchbäume werden für schnelle Suche, Einfügen und Löschen von Elementen verwendet (z.B. bei Leistungstests von Datenoperationen).
• Datenstrukturierung: Darstellung und Organisation von Testdaten oder Ausführungsergebnissen.

Beispiel für die Darstellung eines Knotens in Python:

class Node:
    def __init__(self, value):
        self.value = value  # Wert des Knotens
        self.left = None    # Linkes Kind
        self.right = None   # Rechtes Kind