Traversale algoritmer er avgjørende for å utforske trær og grafer i datavitenskap. De hjelper til med å besøke alle noder systematisk å utføre operasjoner som søk, sortering eller analysestrukturer. Denne guiden gir en trinnvis oversikt over vanlige traversale metoder med eksempelberegninger.

Tre Traversale algoritmer

Treet traversale algoritmer besøker noder i en bestemt rekkefølge. De vanligste metodene er i-orden, forhåndsbestilling og post-ordre traversal. Hver tjener ulike formål og følger en unik besøkssekvens.

Traversal

I rekkefølge traversale besøker venstre undertre, den aktuelle noden, deretter høyre undertre. Det brukes ofte til å hente data i sortert rekkefølge fra binære søketre.

Eksempel: For et binært tre med noder 4, 2, 5, 1, 3 er den i-orden traversale sekvens 1, 2, 3, 4, 5.

Forhåndsbestillings-Traversal

Forhåndsbestillingstransversal besøker den aktuelle noden først, deretter venstre undertre, etterfulgt av høyre undertre. Det er nyttig for kopiering av trær eller å skape prefiksuttrykk.

Eksempel: Ved å bruke det samme treet er pre-ordresekvensen 4, 2, 1, 3, 5.

Post-Order Traversal

Etter bestilling besøker det venstre undertreet, det høyre undertreet, deretter den aktuelle noden. Det brukes ofte til å slette trær eller evaluere postfix-uttrykk.

Eksempel: For det samme treet er post-ordre-sekvensen 1, 3, 2, 5, 4.

Graf Traversale algoritmer

Graftraversale algoritmer utforsker noder i en graf. De to viktigste metodene er Breadth-First Search (BFS) og Deep-First Search (DFS). De brukes i nettverksanalyse, banefinding og mer.

Breadth-First Search (BFS)

BFS utforsker nabonivå på nivå, fra en kildenode. Det bruker en kø for å holde styr på noder til å besøke neste.

Eksempel: BFS besøker noder fra node A i en graf: A, B, C, D, E, basert på deres nærhet.

Dybde-første søk (DFS)

DFS utforsker så langt som mulig langs hver gren før backtracking. Det bruker en stabel eller recitering til å administrere traversal.

Eksempel: Fra node A kan DFS besøke noder i rekkefølge: A, B, D, E, C.