Informatică Algoritmi
Parcurgerea unui arbore in adancime
Parcurgerea unui arbore în adâncime (DFS) explorează nodurile mergând cât mai adânc posibil pe o ramură înainte de a reveni. Se realizează recursiv sau cu stivă, în trei variante: preordine, inordine și postordine.
Variante de parcurgere
- 1 Preordine Vizitează rădăcina, apoi subarborele stâng, apoi subarborele drept. Ordine: rădăcină, stânga, dreapta.
- 2 Inordine Vizitează subarborele stâng, apoi rădăcina, apoi subarborele drept. Ordine: stânga, rădăcină, dreapta.
- 3 Postordine Vizitează subarborele stâng, apoi subarborele drept, apoi rădăcina. Ordine: stânga, dreapta, rădăcină.
Exemplu și aplicații
- Exemplu numeric Pentru arborele cu rădăcina 1, stânga 2 (cu copii 4,5), dreapta 3: preordine dă [1,2,4,5,3], inordine dă [4,2,5,1,3], postordine dă [4,5,2,3,1].
- Implementare Folosește recursie: funcția DFS(nod) dacă nod nu e null, pentru preordine: procesează nod, apelează DFS(stâng), DFS(drept).
- Aplicații Preordine pentru copierea arborilor, inordine pentru arbori de căutare binară (afișează sortat), postordine pentru ștergerea arborilor.
Memorează ordinea variantelor DFS prin exemple practice pentru a le aplica rapid în probleme.