Metodele de traversare a arborilor sunt tehnici folosite pentru a vizita sistematic toate nodurile dintr-o structură de date a arborilor. Înțelegerea acestor metode este esențială pentru diferite aplicații, cum ar fi căutarea, sortarea și evaluarea expresiei. Acest articol compară cele trei metode de traversare primare: preordonare, ordine și postordar, cu calcule practice pentru a ilustra diferențele lor.

Preordine Traversal

Preordine traversează nodul rădăcină mai întâi, apoi recursiv traversează subtree stânga, urmată de subtree dreapta. Această metodă este utilă pentru copierea copacilor sau crearea expresii prefix.

De exemplu, având în vedere copacul:

A[
/
B C
/
D E F

Secvența de traversare preordinală este: A, B, D, E, C, F.

Inordine Traversal

In ordine traversare viziteaza subtree stanga mai intai, apoi nodul de radacina, si in cele din urma subtree dreapta. Aceasta metoda este folosita de obicei pentru copacii de cautare binari pentru a prelua date in ordine sortata.

Folosind acelaşi copac, secvenţa de intersecţie este: D, B, E, A, C, F.

Postorder Traversal

Postorder traversal vizitează subtree-ul stâng, apoi subtree-ul drept, şi în cele din urmă nodul rădăcină. Această abordare este utilă pentru ştergerea copacilor sau evaluarea expresiilor postfix.

De exemplu, secvenţa de traversare postordică este: D, E, B, F, C, A.

Calcule practice

Să ne gândim la copac:

1[
/
2 3
/
4 5 6

Preordine de traversare: 1, 2, 4, 5, 3, 6

In ordine de traversare: 4, 2, 5, 1, 3, 6

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