Tree traversal

In tegenstelling tot gekoppelde lijsten, eendimensionale arrays en andere lineaire gegevensstructuren, die canoniek in lineaire volgorde worden doorlopen, kunnen bomen op meerdere manieren worden doorlopen. Ze kunnen worden doorlopen in de volgorde depth-first of breadth-first. Er zijn drie gebruikelijke manieren om bomen in de “depth-first” volgorde te doorlopen: in volgorde, pre-orde en post-orde. Naast deze basistraversals zijn verschillende complexere of hybride schema’s mogelijk, zoals diepte-gelimiteerde zoekacties zoals iteratief diepte-eerst zoeken. Deze laatste, evenals breadth-first search, kan ook worden gebruikt om oneindige bomen te doorkruisen, zie hieronder.

Gegevensstructuren voor boomtraversalEdit

Het doorkruisen van een boom houdt in dat op een of andere manier over alle knooppunten wordt geiterateerd. Omdat er vanaf een gegeven knooppunt meer dan één mogelijk volgend knooppunt is (het is geen lineaire gegevensstructuur), moeten, uitgaande van sequentieel rekenen (niet parallel), sommige knooppunten op de een of andere manier worden uitgesteld-geslagen voor later bezoek. Dit wordt vaak gedaan via een stapel (LIFO) of een wachtrij (FIFO). Aangezien een boom een zelf-referentiële (recursief gedefinieerde) datastructuur is, kan traverseren worden gedefinieerd door recursie of, subtieler, corecursie, op een zeer natuurlijke en duidelijke manier; in deze gevallen worden de uitgestelde knooppunten impliciet opgeslagen in de aanroepstapel.

Depth-first zoeken is eenvoudig te implementeren via een stapel, inclusief recursief (via de aanroepstapel), terwijl breadth-first zoeken eenvoudig te implementeren is via een wachtrij, inclusief corecursief.:45-61

Depth-first zoeken van een binaire boomEdit

Depth-first traversal (stippelpad) van een binaire boom:

• Pre-order (toegang tot knooppunten op positie rood ●):

  F, B, A, D, C, E, G, I, H;

• In-volgorde (toegang tot knooppunten op positie groen ●):

  A, B, C, D, E, F, G, H, I;

• Post-volgorde (toegang tot knooppunten op positie blauw ●):

  A, C, E, D, B, H, I, G, F.

Deze zoekacties worden “diepte-eerst-zoekacties” (DFS) genoemd, omdat de zoekboom bij elk kind zo diep mogelijk wordt doorzocht voordat naar het volgende broertje of zusje wordt gegaan. Voor een binaire boom worden ze gedefinieerd als toegangsbewerkingen op elke knoop, te beginnen met de huidige knoop, waarvan het algoritme als volgt is:

Het algemene recursieve patroon voor het doorkruisen van een binaire boom is als volgt:

1. Ga één niveau omlaag naar het recursieve argument N. Als N bestaat (niet leeg is) voer dan de volgende drie bewerkingen in een bepaalde volgorde uit: L: Ga recursief door de linker subtree van N. R: de rechter subboom van N recursief doorkruisen. N: Toegang tot (bezoek aan) het huidige knooppunt N zelf.
2. Keer terug door één niveau omhoog te gaan en bij het bovenliggende knooppunt van N aan te komen.

Er zijn drie methoden (patronen) op welke positie van het parcours (traverse) ten opzichte van het knooppunt (in de figuur: rood, groen, of blauw) het bezoek (toegang) van het knooppunt moet plaatsvinden. De keuze van precies één kleur bepaalt precies één bezoek aan een knooppunt, zoals hieronder beschreven. Toegang bij alle drie de kleuren resulteert in een drievoudig bezoek van hetzelfde knooppunt, hetgeen de “all-order” sequentialisatie oplevert:

F-B-A-A-B-D-C-C-D-E-E-D-B-F-G-G- I-H-H- I- I-G-F

Pre-order, NLREdit

1. Toegang tot het gegevensdeel van het huidige knooppunt (in de figuur: positie rood).
2. Doorkruis de linker subtree door recursief de pre-order functie aan te roepen.
3. Doorkruis de rechter subtree door recursief de pre-order functie aan te roepen.

De pre-order traverse is een topologisch gesorteerde traverse, omdat een ouder knooppunt wordt verwerkt voordat een van zijn kind knooppunten wordt gedaan.

In-order, LNREdit

1. Traverseer de linker subtree door recursief de in-order functie op te roepen.
2. Toegang tot het gegevensdeel van het huidige knooppunt (in de figuur: positie groen).
3. Doorkruis de rechter subtree door recursief de in-order functie aan te roepen.

In een binaire zoekboom die zo is geordend dat in elk knooppunt de sleutel groter is dan alle sleutels in de linker subtree en kleiner dan alle sleutels in de rechter subtree, haalt in-order traversal de sleutels op in oplopende gesorteerde volgorde.

Reverse in-order, RNLEdit

1. Traverse the right subtree by recursively calling the reverse in-order function.
2. Access the data part of the current node.
3. Traverse the left subtree by recursively calling the reverse in-order function.

In een binaire zoekboom, haalt reverse in-order traversal de sleutels in aflopende gesorteerde volgorde op.

Post-order, LRNEdit

1. Doorkruis de linker subtree door recursief de post-order functie aan te roepen.
2. Doorkruis de rechter subtree door recursief de post-order functie aan te roepen.
3. Toegang tot het data deel van de huidige node (in de figuur: positie blauw).

Het spoor van een traversal wordt een sequentialisatie van de boom genoemd. Het spoor van de traversal is een lijst van elk bezocht knooppunt. Geen enkele sequentialisatie volgens pre-, in- of post-volgorde beschrijft de onderliggende boom op unieke wijze. Gegeven een boom met verschillende elementen, is ofwel pre-orde ofwel post-orde gekoppeld aan in-orde voldoende om de boom op unieke wijze te beschrijven. Echter, pre-order met post-order laat enige ambiguïteit in de boomstructuur.

Generieke treeEdit

Om een boom te doorkruisen met depth-first search, voert u de volgende bewerkingen uit op elke node:

1. Als node niet aanwezig is, retourneer.
2. Toegang tot (= bezoek aan) knooppunt (pre-order positie).
3. Voor elke i van 1 tot aantal_van_kinderen – 1 doe:
   1. Recursief het i-de kind doorkruisen.
   2. Toegang tot knooppunt (positie binnen_orde).
4. Recursief doorkruisen van laatste kind.
5. Toegang tot knooppunt (positie na_orde).

Afhankelijk van het probleem kunnen de pre-order, post-order, en vooral een van de (aantal_van_kinderen – 1) in-order operaties ongeldig zijn, of is alleen toegang tot een specifiek kind gewenst, zodat deze operaties optioneel zijn. Ook kunnen in de praktijk meer dan één van de pre-order, in-order en post-order operaties nodig zijn. Bijvoorbeeld, bij het invoegen in een ternaire boom, wordt een pre-order operatie uitgevoerd door items te vergelijken. Een post-order operatie kan daarna nodig zijn om de boom opnieuw in evenwicht te brengen.

Breadth-first search, or level orderEdit

Level-order: F, B, G, A, D, I, C, E, H.

Bomen kunnen ook in niveau-volgorde worden doorkruist, waarbij we elk knooppunt op een niveau bezoeken voordat we naar een lager niveau gaan. Dit zoeken wordt breadth-first search (BFS) genoemd, omdat de zoekboom op elke diepte zoveel mogelijk wordt verbreed voordat naar de volgende diepte wordt gegaan.

Andere typesEdit

Er zijn ook boomtraversal-algoritmen die noch als depth-first search noch als breadth-first search kunnen worden geclassificeerd. Eén zo’n algoritme is Monte Carlo tree search, dat zich concentreert op het analyseren van de meest veelbelovende zetten, waarbij de uitbreiding van de zoekboom wordt gebaseerd op willekeurige steekproeven uit de zoekruimte.