0677 - Nivele Bin

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 nivelebinIN.txt 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 nivelebinOUT.txt 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

Exemplul 1:

nivelebinIN.txt

6
2 3 5
6 0 6
1 0 0
7 1 2
4 0 0
10 0 0

nivelebinOUT.txt

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

Exemplul 2:

nivelebinIN.txt

1001
2 3 5
6 0 6
1 0 0
7 1 2
4 0 0
10 0 0

nivelebinOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python" line="1"> def completniv(k, niv, nivele, s, d):

   if k != 0:
       nivele[k] = niv
       completniv(s[k], niv + 1, nivele, s, d)
       completniv(d[k], niv + 1, nivele, s, d)

def verifica_restrictii(n, noduri):

   if not (1 <= n <= 1000):
       return False
   for x, s, d in noduri:
       if x > 1000000 or s > 1000000 or d > 1000000:
           return False
   return True

def main():

   try:
       with open("nivelebinIN.txt", "r") as fin:
           n = int(fin.readline().strip())
           noduri = [tuple(map(int, fin.readline().strip().split())) for _ in range(n)]

           if not verifica_restrictii(n, noduri):
               raise ValueError("Datele nu corespund restrictiilor impuse")

           s = [0] * (n + 1)
           d = [0] * (n + 1)
           p = [0] * (n + 1)
           nivele = [0] * (n + 1)
           
           for i in range(1, n + 1):
               x, s[i], d[i] = noduri[i-1]
               p[s[i]] = 1
               p[d[i]] = 1

           r = 0
           for i in range(1, n + 1):
               if p[i] == 0:
                   r = i
                   break

           completniv(r, 0, nivele, s, d)
           
           nivmax = max(nivele)

           with open("nivelebinOUT.txt", "w") as fout:
               fout.write(f"{nivmax + 1}\n")
               for niv in range(nivmax + 1):
                   k = sum(1 for j in range(1, n + 1) if nivele[j] == niv)
                   fout.write(f"{k} ")

   except ValueError as e:
       with open("nivelebinOUT.txt", "w") as fout:
           fout.write(str(e))

if __name__ == "__main__":

   main()

</syntaxhighlight>