Boomdoorgangsmethoden zijn technieken die worden gebruikt om alle knooppunten in een boomdatastructuur systematisch te bezoeken. Het begrijpen van deze methoden is essentieel voor verschillende toepassingen zoals zoeken, sorteren en expressie-evaluatie. Dit artikel vergelijkt de drie primaire doorloopmethoden: voorbestelling, in volgorde en postorder, met praktische berekeningen om hun verschillen te illustreren.

Voororde Traversal

De voororde doorkruist eerst de wortelknop, en dan recursief de linker subboom, gevolgd door de rechter subboom. Deze methode is nuttig voor het kopiëren van bomen of het creëren van prefix-expressies.

Bijvoorbeeld, gezien de boom:

A
/
B C
/
D E F

De voororde traversale volgorde is: A, B, D, E, C, F.

Inorder Traversal

In volgorde van doorkruisen bezoekt de linker subboom eerst, dan de wortelknoop, en tenslotte de rechter subboom. Deze methode wordt vaak gebruikt voor binaire zoekbomen om gegevens in gesorteerde volgorde op te halen.

Met dezelfde boom is de orde van de traversale volgorde: D, B, E, A, C, F.

Postorder Traversal

Postorder doorkruist de linker subboom, dan de rechter subboom, en tenslotte de wortelknoop. Deze benadering is nuttig voor het verwijderen van bomen of het evalueren van postfix-uitdrukkingen.

Voor de voorbeeldboom is de postorder traversale volgorde: D, E, B, F, C, A.

Praktische berekeningen

Denk aan de boom:

1
/
2 3
/
4 5 6

Voororde doorkruising: 1, 2, 4, 5, 3, 6

Inorder traversal: 4, 2, 5, 1, 3, 6

Postorder doorkruising: 4, 5, 2, 6, 3, 1