Tot hiertoe leerden we over lineaire datastructuren, waarbij soms de volgorde van de elementen van belang was, zoals lijsten, stapels en wachtrijen. In die datastructuren zijn de gegevens sequentieel, opeenvolgend georganiseerd.

In dit hoofdstuk bespreken we voor het eerst een niet-lineaire datastructuur, waarin de gegevens op een hiërarchische manier georganiseerd zijn: de boom.

🌳 Definitie - Boom

Een boom (tree in het Engels) is een niet-lineaire datastructuur die bestaat uit knopen en takken die op een hiërarchische manier met elkaar verbonden zijn.

De onderdelen van een boom

De benamingen voor de onderdelen van een boom komen overeen met die uit de biologie.

• We spreken over (interne) knopen (nodes in het Engels) van de boom als er nieuwe vertakkingen ontstaan.
• Takken (edges in het Engels) verbinden de knopen met elkaar.
• De uiteinden van de boom noemen we bladeren (leaves in het Engels).

👀 Voorbeeld - Boom van hondenrassen 🐕

We duiden de interne knopen, takken en bladeren aan in de boom van de hondenrassen.

• (interne) knopen: wolf, Europese rassen, Aziatische rassen, herdershonden, jachthonden, sporthonden, werkhonden
• bladeren: moderne wolf, pekinees, chow chow, , bordercollie, duitse herder, beagle, bloedhond, teckel, Engelse cockerspaniël, labrador retriever, boxer, dobermann, husky, berner sennen
• takken: de verbinding

🪢 Definitie - Knoop

Een knoop in een boomstructuur heeft maximaal één ouderlijke knoop (parent node in het Engels). Een knoop heeft ook nul of meer kindknopen (child nodes in het Engels) die vlak onder deze knoop staan in de hiërarchie. De ouderlijke knoop staat in de hiërarchie vlak boven de knoop, en de kindknoop vlak onder de knoop.

🥕 Definitie - Wortel

Een knoop zonder ouderlijke knoop wordt de wortel van de boom genoemd.

🧠 Denkoefening - Wortel van hondenrassen

Welke knoop is de wortelknoop in de boom van hondenrassen?