# PBinfo #677 – NiveleBin – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Considerăm un arbore binar cu n noduri în care fiecare nod este numerotat de la 1 la n și conține o valoare număr natural. În acest arbore rădăcina este considerată pe nivelul 0, descendenții direcți ai rădăcinii pe nivelul 1, etc. Să se determine numărul de nivele k din arbore și, pentru fiecare nivel i de la 0 la k, numărul de noduri situate pe acel nivel.

Date de intrare
Fișierul de intrare nivelebin.in conține pe prima linie numărul n. Fiecare dintre următoarele n linii conține câte 3 numere X st dr; linia i + 1 din fișier conține informațiile despre nodul numerotat cu i: X reprezintă valoare din nod, st reprezintă numărul de ordine al descendentului stâng sau 0 dacă nodul i nu are descendent stâng, iar dr reprezintă numărul de ordine al descendentului drept sau 0 dacă nodul i nu are descendent drept.

Date de ieșire
Fișierul de ieșire nivelebin.out va conține pe prima linie numărul k, iar pe a doua linie k+1 numere naturale separate prin exact un spațiu, al i-lea număr reprezentând numărul de noduri situate pe nivelul i-1 din arbore.

Restricții și precizări

1 ≤ n ≤ 1000
valorile din nodurile arborelui vor fi mai mici sau egale cu 1.000.000

Exemplu:
nivelebin.in

6
2 3 5
6 0 6
1 0 0
7 1 2
4 0 0
10 0 0
nivelebin.out

3
1 2 3
Explicație
Exemplul corespunde arborelui de mai jos, în care au fost marcate cu albastru valorile din noduri, iar cu roșu numerele de ordine ale nodurilor.



Arborele conține trei nivele:


nivelul 0 conține doar rădăcina, nodul numerotat cu 4
nivelul 1 conține două noduri, cele numerotate cu 1 2
nivelul 2 conține trei noduri, cele numerotate cu 3 5 6

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
#define NN 1005
using namespace std;
ifstream fin("nivelebin.in");
ofstream fout("nivelebin.out");
int n, info[NN], st[NN], dr[NN];
int v[NN], nv;
void citire()
{
	fin >> n;
	for(int i =1 ; i <= n ; ++i)
		fin >> info[i] >> st[i] >> dr[i];
}
int radacina()
{
	int v[NN];
	for(int i =1 ; i <= n ; ++i)
		v[i] = 0;
	for(int i = 1 ; i <= n ; ++i)
	{
		if(st[i] != 0)
			v[st[i]] = 1;
		if(dr[i] != 0)
			v[dr[i]] = 1;
	}
	for(int i = 1 ; i <= n ; ++i)
		if(v[i] == 0)
			return i;
	return 0;
}
void parcurgere(int x, int niv)
{
	if (x)
	{
		v[niv]++;
		if(niv > nv)
			nv = niv;
		parcurgere(st[x] , niv + 1);
		parcurgere(dr[x] , niv + 1);
	}
}
int main()
{
	citire();
	parcurgere(radacina() , 0);
	fout << nv + 1 << endl;
	for(int i = 0 ; i <= nv ; i ++)
		fout << v[i] << " ";
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/677)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/677/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-677/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)