Czym jest drzewo binarne?

Drzewo binarne to struktura danych w kształcie drzewa, w której każdy węzeł ma co najwyżej dwa potomki: lewego i prawego.

Kluczowe cechy:

• Każdy węzeł ma wskaźnik na wartość (dane) oraz wskaźniki na lewego i prawego potomka (mogą być puste).
• Istnieje węzeł korzeniowy — górny węzeł drzewa, nie mający przodka.
• Liście to węzły nieposiadające potomków.
• Poddrzewa to każde poddrzewo korzenia drzewa binarnego, które również jest drzewem binarnym.

Główne typy drzew binarnych:

• Drzewo binarne pełne: na każdym poziomie, z wyjątkiem być może ostatniego, wszystkie węzły mają dwóch potomków, a na ostatnim poziomie wszystkie węzły są przesunięte w lewo.
• Drzewo binarne doskonałe: wszystkie poziomy są w pełni wypełnione, a każdy węzeł (z wyjątkiem liści) ma dwóch potomków.
• Drzewo binarne zrównoważone: wysokości lewego i prawego poddrzewa każdego węzła różnią się nie więcej niż o 1.

Zastosowania w QA:

• Hierarchia testów: organizacja scenariuszy testowych lub zestawów testów w strukturze drzewiastej dla lepszej czytelności i nawigacji.
• Wyszukiwanie i sortowanie danych: drzewa binarne wyszukiwań są używane do szybkiego wyszukiwania, wstawiania i usuwania elementów (np. podczas testowania wydajności operacji na danych).
• Strukturyzacja danych: reprezentacja i organizacja danych testowych lub wyników wykonania.

Przykład reprezentacji węzła w Pythonie:

class Node:
    def __init__(self, value):
        self.value = value  # Wartość węzła
        self.left = None    # Lewy potomek
        self.right = None   # Prawy potomek