Co je to binární strom?

Binární strom je datová struktura ve tvaru stromu, kde každý uzel má nejvýše dva potomky: levého a pravého.

Klíčové vlastnosti:

• Každý uzel má ukazatel na svou hodnotu (data) a ukazatele na levého a pravého potomka (mohou být prázdné).
• Existuje kořenový uzel — horní uzel stromu, bez předka.
• Listy jsou uzly bez potomků.
• Podstromy jsou každý z binárních stromů, které tvoří podstrom kořenového stromu.

Hlavní typy binárních stromů:

• Kompletní binární strom: na každé úrovni, s výjimkou možná poslední, mají všechny uzly dva potomky, a na poslední úrovni jsou všechny uzly posunuty vlevo.
• Dokonalý binární strom: všechny úrovně jsou plně zaplněny, a každý uzel (kromě listů) má dva potomky.
• Vyvážený binární strom: výšky levého a pravého podstromu každého uzlu se liší nejvýše o 1.

Použití v QA:

• Hierarchie testů: organizace testovacích scénářů nebo sad testů do stromové struktury pro lepší čitelnost a navigaci.
• Vyhledávání a třídění dat: binární vyhledávací stromy se používají pro rychlé vyhledávání, vkládání a odstraňování prvků (například při testování výkonu operací s daty).
• Strukturování dat: reprezentace a organizace testovacích dat nebo výsledků provedení.

Příklad reprezentace uzlu v Pythonu:

class Node:
    def __init__(self, value):
        self.value = value  # Hodnota uzlu
        self.left = None    # Levý potomek
        self.right = None   # Pravý potomek