Informatică Alte teme
Parcurgerea arborilor inordine preordine postordine
Parcurgerea arborilor binari este o metodă de vizitare a nodurilor într-o ordine specifică, folosită în algoritmi și structuri de date. Cele trei tipuri principale sunt înordine, preordine și postordine, fiecare cu o regulă de parcurgere. Acestea sunt esențiale pentru operații ca căutarea sau sortarea.
Reguli de parcurgere
- Preordine Vizitează rădăcina, apoi subarborele stâng, apoi subarborele drept. Ordinea: rădăcină, stânga, dreapta.
- Înordine Vizitează subarborele stâng, apoi rădăcina, apoi subarborele drept. Ordinea: stânga, rădăcină, dreapta.
- Postordine Vizitează subarborele stâng, apoi subarborele drept, apoi rădăcina. Ordinea: stânga, dreapta, rădăcină.
Exemplu numeric
- 1 Pasul 1: Construiește arborele Consideră un arbore binar cu rădăcina A, copil stâng B (cu copii D, E), și copil drept C (cu copil F).
- 2 Pasul 2: Aplică preordine Preordine: A, B, D, E, C, F. Rădăcina A, apoi subarborele lui B (D, E), apoi subarborele lui C (F).
- 3 Pasul 3: Aplică înordine Înordine: D, B, E, A, C, F. Subarborele stâng (D, B, E), apoi rădăcina A, apoi subarborele drept (C, F).
- 4 Pasul 4: Aplică postordine Postordine: D, E, B, F, C, A. Subarborele stâng (D, E, B), apoi subarborele drept (F, C), apoi rădăcina A.
Exersează parcurgerile desenând arbori simple și notând ordinea nodurilor pentru a le memora.