Question

Se citeste de la tastatura un numar natural n,reprezentand numarul de noduri ale unui arbore si un vector v ,reprezentand vectorul de tati. Sa se afiseze inaltimea arborelui.
De exemplu :
9
0 1 1 1 2 3 4 4 5
Se va afisa valoarea 4.

Answer 1

Ai in poze cateva exemple si modul de lucru pe unul din ele.

Codul (probabil il va afisa site-ul fara indentare )

#include <iostream>
using namespace std;
//Citirea vectorului de tativoid citire (int v[] ,int n){int i ;     for(i=1;i<=n;i++)         cin>>v[i];}//Se numeşte înălţimea unui arbore diferenţa dintre nivelul maxim din arbore şi nivelul minim
//Urmatorul subprogram determina inaltimea arborelui ( distanta maxima dintre o frunza si radacina ) si returneaza valoareaint inaltime(int v[] ,int n){int i , j ,inalt_maxima=0,inaltime_curenta;    for(i=1;i<=n;i++){       //Pentru fiecare nod , calculezi distanta de la acel nod la radacina(lungimea ramurii)        inaltime_curenta=0;  //Initializam valoarea variabilei care retine lungimea pentru un anumit i cu 0 la fiecare iteratie        j=i;                 //variabila j primeste numarul nodului curent        while(v[j]){         //Cat timp valoarea asociata pozitiei j este diferita de 0 ( tatal este diferit de 0)            inaltime_curenta++;            j=v[j];}        //j primeste numarul tatalui sau        if(inaltime_curenta>inalt_maxima)  //Daca lungimea rezultata e mai mare decat maximul .....              inalt_maxima=inaltime_curenta;}    return inalt_maxima+1;} //Returneaza +1 deoarece inalt_maxima returneaza numarul de muchii din cel mai lung drum de la radacina la o frunza (Daca ai 3 muchii is 4 noduri , etc )
//Fix chestia asta ->orice  arbore are inaltimea = 1 + inaltimea celei mai lungi ramuri(lungimea , tot aia )
/*Ce face e ca ia practic fiecare nod din graf si merge in sus ( din tata in tata ) pana da de radacina (0) . Daca e verificat fix nodu radacinaatunci inalt_curenta va fi 0 , samd */int main(){int n; cin>>n; int v[n+1]; citire(v,n); cout<<inaltime(v,n);}