Parcurgerea arborelui

Parcurgerea unui arbore vizitează nodurile după o regulă. Într-o parcurgere în adâncime pornim din rădăcină și explorăm complet fiecare subarbore înainte de următorul; într-o parcurgere pe niveluri vizităm rădăcina, apoi fiii, apoi nepoții. Ordinea exactă între frați depinde de ordinea în care sunt păstrați.

Parcurgerea unui arbore vizitează fiecare nod o singură dată, după o regulă fixă. Parcurgerea în adâncime explorează complet un subarbore înainte de următorul și se scrie natural recursiv. Parcurgerea în lățime (pe niveluri) vizitează întâi rădăcina, apoi fiii ei, apoi nepoții, și folosește o coadă. În arborele binar, momentul vizitării rădăcinii dă trei variante de adâncime: preordine RSD (rădăcină, stânga, dreapta), inordine SRD (stânga, rădăcină, dreapta) și postordine SDR (stânga, dreapta, rădăcină). La fiecare apel se aplică aceeași regulă în subarborele stâng și în cel drept, iar un subarbore gol nu produce nimic. Toate parcurgerile cer $O(n)$ timp, deoarece fiecare nod este vizitat o dată.

Exemplul 1 — arbore binar. Arborele are rădăcina A, fiul stâng B și fiul drept C, iar B are fiul drept D:

#include <iostream>
#include <queue>
using namespace std;
struct Nod { char v; Nod *s, *d; };
void pre(Nod* p) { if (!p) return; cout << p->v << " "; pre(p->s); pre(p->d); }
void ino(Nod* p) { if (!p) return; ino(p->s); cout << p->v << " "; ino(p->d); }
void post(Nod* p) { if (!p) return; post(p->s); post(p->d); cout << p->v << " "; }
void latime(Nod* r) {
    queue<Nod*> q;
    q.push(r);
    while (!q.empty()) {
        Nod* p = q.front();
        q.pop();
        cout << p->v << " ";
        if (p->s) q.push(p->s);
        if (p->d) q.push(p->d);
    }
}
int main() {
    Nod d{'D', nullptr, nullptr}, c{'C', nullptr, nullptr};
    Nod b{'B', nullptr, &d}, a{'A', &b, &c};
    pre(&a); cout << "\n";
    ino(&a); cout << "\n";
    post(&a); cout << "\n";
    latime(&a);
}

Se afișează A B D C (preordine), B D A C (inordine), D B C A (postordine) și A B C D (în lățime). Cele patru liste conțin aceleași noduri, în ordini diferite. Coada din parcurgerea în lățime păstrează nodurile descoperite și încă nevizitate: după A intră B și C, după B intră D.

Exemplul 2 — arbore oarecare. Arborele are rădăcina 1, fiii lui 1 sunt 2 și 3, fiii lui 2 sunt 4 și 5, iar fiul lui 3 este 6. Pentru un arbore oarecare nu există „inordine”, deoarece un nod poate avea mai mult de doi fii; rămân preordinea, postordinea și parcurgerea în lățime, iar ordinea fiilor este ordinea din listele de fii:

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> f[7];
void pre(int x) {
    cout << x << " ";
    for (int y : f[x]) pre(y);
}
void post(int x) {
    for (int y : f[x]) post(y);
    cout << x << " ";
}
int main() {
    f[1] = {2, 3};
    f[2] = {4, 5};
    f[3] = {6};
    pre(1); cout << "\n";
    post(1); cout << "\n";
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        cout << x << " ";
        for (int y : f[x]) q.push(y);
    }
}

Se afișează 1 2 4 5 3 6 (preordine), 4 5 2 6 3 1 (postordine) și 1 2 3 4 5 6 (în lățime). Dacă listele fiilor s-ar memora în altă ordine, de exemplu f[1] = {3, 2}, preordinea ar deveni 1 3 6 2 4 5: ordinea între frați face parte din răspuns. În parcurgerea în lățime nodurile apar în ordinea nivelurilor: nivelul 0 are nodul 1, nivelul 1 are 2 și 3, iar nivelul 2 are 4, 5 și 6.

Exemplul 3 — refacerea arborelui din două parcurgeri. Preordinea A B D C și inordinea B D A C determină un singur arbore binar. A, primul din preordine, este rădăcina; în inordine B și D sunt înaintea lui A, deci formează subarborele stâng, iar C este în dreapta. O singură parcurgere nu ajunge: A cu fiul stâng B și A cu fiul drept B au aceeași preordine, A B.

Exemplu în formatul examenului. Un arbore cu rădăcina 1 are fiii 2 și 3 ai lui 1, fiii 4 și 5 ai lui 2 și fiul 6 al lui 3, în această ordine a fiilor. Care este parcurgerea în postordine?

• a) 4 5 2 6 3 1
• b) 1 2 4 5 3 6
• c) 1 2 3 4 5 6
• d) 4 2 5 1 6 3

Răspunsul corect este a). În postordine se vizitează întâi toți descendenții unui nod, apoi nodul. Subarborele lui 2 dă 4 5 2, subarborele lui 3 dă 6 3, iar rădăcina 1 se vizitează ultima. Varianta b) este preordinea, c) este parcurgerea în lățime, iar d) este o inordine (stânga, nod, dreapta) a arborelui privit ca binar, cu 6 ca fiu stâng al lui 3, nu o postordine.

Greșeli frecvente

• Greșit: toate parcurgerile vizitează nodurile în aceeași ordine.
  Corect: regula de explorare poate schimba ordinea.
• Greșit: preordinea vizitează nodul după toți descendenții.
  Corect: îl vizitează înainte.
• Greșit: ordinea între frați este independentă de ordinea listelor de fii.
  Corect: depinde de ordinea în care sunt memorați fiii.

Înainte și după