Tret traversale metoder er teknikker som brukes til å besøke alle noder i en tre data struktur systematisk. Forstå disse metodene er avgjørende for ulike applikasjoner som søking, sortering og uttrykksvurdering. Denne artikkelen sammenligner de tre primære traversale metodene: forhåndsbestilling, i orden og postordre, med praktiske beregninger for å illustrere deres forskjeller.

Forhåndsbestille Traversal

Forhåndsbestille traversale besøker rotknuten først, deretter krysser rekursivt det venstre undertreet, etterfulgt av høyre undertre. Denne metoden er nyttig for kopiering av trær eller å skape prefiksuttrykk.

For eksempel, gitt treet:

A
/
B C
] /
D E F

Den forordnede traversalsekvensen er: A, B, D, E, C, F.

Indordne Traversal

Ordne traversale besøker venstre undertre først, deretter rotnoden, og til slutt høyre undertre. Denne metoden brukes vanligvis for binære søketre til å hente data i sortert rekkefølge.

Ved å bruke det samme treet er den inordnede traversale sekvensen: D, B, E, A, C, F.

Postordre Traversal

Postordre traversal besøker venstre undertre, deretter høyre undertre, og til slutt rotnode. Denne tilnærmingen er nyttig for å slette trær eller evaluere postfix uttrykk.

For eksempel er den postordre traversale sekvensen: D, E, B, F, C, A.

Praktiske beregninger

Tenk på treet:

1
/
2 3
] /
4 5 6

Forhåndsbestilling: 1, 2, 4, 5, 3, 6

Innbestillingsvogn: 4, 2, 5, 1, 3, 6

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