Primești un arbore cu 8 noduri, dat ca la bac: un vector în care, pentru fiecare nod, scrie cine e tatăl lui. Programul găsește rădăcina, frunzele și înălțimea.
Al doilea rând e vectorul de tați: tatăl lui 1 e 3, tatăl lui 2 e 3, nodul 3 nu are tată, și tot așa. Desenat, arborele arată așa:
Arborele din exemplu
3
/ | \
1 2 4
/ \ |
5 6 7
|
8
să citești un arbore dat prin vectorul de tați
să găsești rădăcina, fiii unui nod și frunzele
să urci din nod în nod până la rădăcină
să calculezi nivelul unui nod și înălțimea arborelui
Pasul 2 din 5
Rulează-l linie cu linie
Un arbore mai mic, cu 5 noduri. Rădăcina e singurul nod fără tată, adică cel cu 0 în vector.
radacina.cpp
#include<iostream>usingnamespace std;intmain() {int t[6] = {0, 3, 3, 0, 3, 1};int n = 5, rad = 0;for (int k = 1; k <= n; k++)if (t[k] == 0) rad = k; cout << rad;return0;}
Variabile
Ce apare pe ecran
Linia 5. Vectorul de tați, folosit de la poziția 1. t[0] e doar un loc liber, ca nodurile să se numere de la 1.
Linia 6. 5 noduri. rad va ține rădăcina găsită.
Linia 7. Se verifică nodul 1.
Linia 8.t[1] e 3: nodul 1 are tată, deci nu e rădăcina.
Linia 7. Nodul 2.
Linia 8.t[2] e tot 3. Nodul 3 are deja doi fii.
Linia 7. Nodul 3.
Linia 8.t[3] e 0: nodul 3 nu are tată.
Linia 9. Am găsit rădăcina: rad devine 3.
Linia 7. Nodul 4.
Linia 8.t[4] e 3, încă un fiu al rădăcinii.
Linia 7. Nodul 5.
Linia 8.t[5] e 1: tatăl lui 5 e nodul 1.
Linia 7.k ar fi 6, iar 6 <= 5 e fals. Bucla se termină.
Linia 10. Se afișează rădăcina.
Linia 11.main se încheie.
Gata. Într-un arbore cu rădăcină există exact un nod cu tatăl 0.
Prezice ieșirea
În același arbore, câți fii are nodul 3?
Răspuns: 3.
Fiii lui 3 sunt nodurile i pentru care t[i] == 3: 1, 2 și 4. Numărul de fii al unui nod e de câte ori apare el în vectorul de tați.
Pasul 3 din 5
Ce afli din vectorul de tați
Fragmentele stau în main și folosesc arborele cu 8 noduri de la pasul 1.
1
Cuvintele de bază
Termenii folosiți la arbori
Termen
În vectorul de tați
rădăcina
nodul cu t[i] == 0
tatăl lui x
t[x]
fiii lui x
nodurile i cu t[i] == x
frunză
nod care nu apare în vector
Un arbore cu n noduri are n − 1 muchii: fiecare nod, în afară de rădăcină, e legat de tatăl lui. De aceea un singur vector ajunge ca să-l descrie tot.
2
Fiii unui nod și frunzele
fii.cpp
int t[9] = {0, 3, 3, 0, 3,1, 1, 4, 7};int n = 8, x = 1;cout << "Fiii lui " << x << ": ";for (int k = 1; k <= n; k++)if (t[k] == x) cout << k << ' ';cout << "\nFrunze: ";for (int k = 1; k <= n; k++) {bool frunza = true;for (int p = 1; p <= n; p++)if (t[p] == k) frunza = false;if (frunza) cout << k << ' ';}
Ce apare pe ecran
Fiii lui 1: 5 6
Frunze: 2 5 6 8
Fiii se găsesc într-o singură parcurgere. Pentru frunze, fiecare nod e căutat în tot vectorul: dacă nimeni nu-l are drept tată, e frunză. Două bucle una în alta, deci n · n pași.
x = t[x] urcă un nivel. Bucla se oprește la rădăcină, când tatăl e 0. Numărul de urcări e nivelul nodului: rădăcina are nivelul 0, fiii ei nivelul 1.
4
Înălțimea arborelui
inaltime.cpp
int t[9] = {0, 3, 3, 0, 3,1, 1, 4, 7};int n = 8, h = 0;for (int k = 1; k <= n; k++) {int x = k, niv = 0;while (t[x] != 0) { x = t[x]; niv++; }if (niv > h) h = niv;}cout << h;
Ce apare pe ecran
3
Înălțimea e cel mai mare nivel al unui nod, adică cel mai lung drum de la rădăcină la o frunză, numărat în muchii. Aici, drumul 3–4–7–8. Citește atent enunțul: unele probleme numără nivelurile, nu muchiile, și atunci răspunsul e 4.
Capcană: vectorul citit de la 0
Nodurile sunt numerotate de la 1, dar valorile au fost citite în t[0]…t[4]. Fiecare tată ajunge în dreptul altui nod:
zero.cpp
#include<iostream>usingnamespace std;intmain() {int t[6], n = 5;for (int k = 0; k < n; k++) cin >> t[k];int rad = 0;for (int k = 1; k <= n; k++)if (t[k] == 0) rad = k; cout << "Rădăcina: " << rad;return0;}
Cu 3 3 0 3 1
Rădăcina: 2
Rădăcina corectă e 3. Repară citind cu for (int k = 1; k <= n; k++), cu același indice pe care îl folosești peste tot.
Capcană: urci un pas în plus
Condiția x != 0 numără și pasul de la rădăcină la „tatăl” ei inexistent, 0. Nodul 5 are nivelul 2, dar programul afișează:
Tatăl 4 apare la nodurile 1 și 2, tatăl 3 la nodurile 4 și 5. Patru noduri îndeplinesc condiția.
Pasul 5 din 5
Ce ai învățat
Vectorul de tați ține, pentru fiecare nod, tatăl lui. Rădăcina are 0.
Fiii lui x sunt nodurile cu t[i] == x. Frunzele nu apar deloc în vector.
x = t[x] urcă un nivel. Te oprești când t[x] e 0.
Înălțimea e nivelul maxim, numărat în muchii. Verifică în enunț cum se numără.
Programul complet
Vectorul e global, ca funcțiile nivel și frunza să-l poată folosi fără parametri în plus. Funcțiile fac programul principal scurt și ușor de verificat.
arbore.cpp
#include<iostream>usingnamespace std;int t[101], n;intnivel(int x) {int niv = 0;while (t[x] != 0) { x = t[x]; niv++; }return niv;}boolfrunza(int x) {for (int k = 1; k <= n; k++)if (t[k] == x)returnfalse;returntrue;}intmain() { cin >> n;for (int k = 1; k <= n; k++) cin >> t[k];int rad = 0, h = 0;for (int k = 1; k <= n; k++) {if (t[k] == 0) rad = k;if (nivel(k) > h) h = nivel(k); } cout << "Rădăcina: " << rad; cout << "\nFrunze:";for (int k = 1; k <= n; k++)if (frunza(k)) cout << ' ' << k; cout << "\nÎnălțime: " << h;return0;}