Wat is een binaire boom?

Een binaire boom is een datastructuur in de vorm van een boom waarin elke knoop maximaal twee kinderen heeft: links en rechts.

Belangrijke kenmerken:

• Elke knoop heeft een pointer naar zijn waarde (gegevens) en pointers naar zijn linker- en rechterkinderen (kunnen leeg zijn).
• Er bestaat een wortelknoop — de bovenste knoop van de boom, zonder voorouder.
• Bladeren zijn knopen zonder kinderen.
• Subbomen zijn elk van de binaire bomen die de wortelboom vormen.

Belangrijkste typen binaire bomen:

• Volledige binaire boom: op elk niveau, behalve mogelijk het laatste, hebben alle knopen twee kinderen, en op het laatste niveau zijn alle knopen naar links verschoven.
• Perfecte binaire boom: alle niveaus zijn volledig gevuld, en elke knoop (behalve bladeren) heeft twee kinderen.
• Gebalanceerde binaire boom: de hoogtes van de linker- en rechteronderbomen van elke knoop verschillen niet meer dan 1.

Toepassingen in QA:

• Testhiërarchie: organisatie van testscenario's of testsets in een boomstructuur voor betere leesbaarheid en navigatie.
• Gegevens zoeken en sorteren: binaire zoekbomen worden gebruikt voor snelle zoekopdrachten, invoegen en verwijderen van elementen (bijvoorbeeld bij prestatietests van gegevensoperaties).
• Gegevensstructurering: voorstelling en organisatie van testgegevens of uitvoeringsresultaten.

Voorbeeld van een knooprepresentatie in Python:

class Node:
    def __init__(self, value):
        self.value = value  # Waarde van de knoop
        self.left = None    # Linker kind
        self.right = None   # Rechter kind