MyCodeSchool

Pasul 1 din 5

C++

Pasul 1 din 5 · Ce construiești

  • C++
  • BAC
  • 14 minute

Arbori în C++: vectorul de tați

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.

arbore.cpp, în consolă
8
3 3 0 3 1 1 4 7
Rădăcina: 3
Frunze: 2 5 6 8
Înălțime: 3

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

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>using namespace std;int main() {    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;    return 0;}

Variabile

Ce apare pe ecran


      

  1. 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.
  2. Linia 6. 5 noduri. rad va ține rădăcina găsită.
  3. Linia 7. Se verifică nodul 1.
  4. Linia 8. t[1] e 3: nodul 1 are tată, deci nu e rădăcina.
  5. Linia 7. Nodul 2.
  6. Linia 8. t[2] e tot 3. Nodul 3 are deja doi fii.
  7. Linia 7. Nodul 3.
  8. Linia 8. t[3] e 0: nodul 3 nu are tată.
  9. Linia 9. Am găsit rădăcina: rad devine 3.
  10. Linia 7. Nodul 4.
  11. Linia 8. t[4] e 3, încă un fiu al rădăcinii.
  12. Linia 7. Nodul 5.
  13. Linia 8. t[5] e 1: tatăl lui 5 e nodul 1.
  14. Linia 7. k ar fi 6, iar 6 <= 5 e fals. Bucla se termină.
  15. Linia 10. Se afișează rădăcina.
  16. Linia 11. main se încheie.
  17. 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.

Cuvintele de bază

Termenii folosiți la arbori
TermenÎn vectorul de tați
rădăcinanodul cu t[i] == 0
tatăl lui xt[x]
fiii lui xnodurile 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.

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.

Urci spre rădăcină

nivel.cpp
int t[9] = {0, 3, 3, 0, 3,            1, 1, 4, 7};int x = 8, niv = 0;cout << "Drumul: " << x;while (t[x] != 0) {    x = t[x];    niv++;    cout << ' ' << x;}cout << "\nNivel: " << niv;

Ce apare pe ecran

Drumul: 8 7 4 3
Nivel: 3

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.

Î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>using namespace std;int main() {    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;    return 0;}

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ă:

nivel0.cpp
#include <iostream>using namespace std;int main() {    int t[6] = {0, 3, 3, 0, 3, 1};    int x = 5, niv = 0;    while (x != 0) {        x = t[x];        niv++;    }    cout << niv;    return 0;}

Ce apare pe ecran

3

Repară cu while (t[x] != 0): te oprești când ai ajuns la rădăcină, nu după ea.

Pasul 4 din 5

Verifică-te

Cinci grile în stilul subiectului I. Ajută să desenezi arborele pe o foaie.

1 din 5 · Alege varianta

Un arbore are vectorul de tați (2, 0, 2, 1, 1). Care e rădăcina?

Răspuns: nodul 2.

Pe poziția 2 e valoarea 0, deci nodul 2 nu are tată. 0 nu e un nod, ci semnul că tatăl lipsește.

2 din 5 · Alege varianta

Câte frunze are arborele cu vectorul de tați (2, 0, 2, 1, 1)?

Răspuns: 3.

În vector apar doar 2 și 1, deci doar ele au fii. Nodurile 3, 4 și 5 nu apar nicăieri: sunt frunze.

3 din 5 · Prezice ieșirea

Ce afișează programul?

nivel.cpp
#include <iostream>using namespace std;int main() {    int t[6] = {0, 2, 0, 2, 1, 1};    int x = 5, niv = 0;    while (t[x] != 0) {        x = t[x];        niv++;    }    cout << niv;    return 0;}

Răspuns: „2”.

Drumul e 5, 1, 2: două urcări. Bucla se oprește la nodul 2, pentru că t[2] e 0.

4 din 5 · Alege varianta

Într-un vector de tați corect, pentru un arbore cu rădăcină, câte valori de 0 există?

Răspuns: exact una.

Doar rădăcina nu are tată. Două valori 0 ar însemna două bucăți separate, adică o pădure, nu un arbore.

5 din 5 · Prezice ieșirea

Ce afișează programul? Numără câți fii au, împreună, nodurile 3 și 4.

fii.cpp
#include <iostream>using namespace std;int main() {    int t[8] = {0, 4, 4, 0,                3, 3, 1, 1};    int c = 0;    for (int i = 1; i <= 7; i++)        if (t[i] == 4 || t[i] == 3)            c++;    cout << c;    return 0;}

Răspuns: „4”.

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

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>using namespace std;int t[101], n;int nivel(int x) {    int niv = 0;    while (t[x] != 0) {        x = t[x];        niv++;    }    return niv;}bool frunza(int x) {    for (int k = 1; k <= n; k++)        if (t[k] == x)            return false;    return true;}int main() {    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;    return 0;}

Cu datele de la pasul 1

Rădăcina: 3
Frunze: 2 5 6 8
Înălțime: 3

Continuă cu