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

Exemplul 2

nivelebinin.txt

7

1 2 3

2 4 0

3 5 6

4 0 0

5 7 0

6 0 0

7 0 0

nivelebinout.txt

3

1 2 4

Rezolvare

<syntaxhighlight lang="python" line>

1. 0677 - Nivele Bin

class TreeNode:

   def __init__(self, value, left=None, right=None):
       self.value = value
       self.left = left
       self.right = right

def read_tree_from_file(file):

   n = int(file.readline())
   if not (1 <= n <= 1000):
       return None

   nodes = [None]  # index 0 nu este folosit

   for i in range(1, n + 1):
       x, st, dr = map(int, file.readline().split())
       if not (1 <= x <= 1000000):
           return None
       if not (0 <= st <= n):
           return None
       if not (0 <= dr <= n):
           return None
       nodes.append(TreeNode(x, st, dr))

   return nodes

def calculate_levels_and_counts(root, nodes):

   levels_counts = {}
   stack = [(root, 0)]  # Stivă de noduri și niveluri

   while stack:
       node, level = stack.pop()

       if level not in levels_counts:
           levels_counts[level] = 1
       else:
           levels_counts[level] += 1

       if nodes[node].left:
           stack.append((nodes[node].left, level + 1))
       if nodes[node].right:
           stack.append((nodes[node].right, level + 1))

   return levels_counts

def check_restrictions(n):

   return 1 <= n <= 1000

def main():

   with open('nivelebinin.txt', 'r') as file:
       n = int(file.readline())
       if not check_restrictions(n):
           print("false")
           return

       nodes = read_tree_from_file(file)
       if nodes is None:
           print("false")
           return

       root = 1  # Rădăcina arborelui
       levels_counts = calculate_levels_and_counts(root, nodes)

       k = len(levels_counts) - 1  # Numărul de niveluri
       counts_list = [levels_counts[i] for i in range(k + 1)]

   with open('nivelebinout.txt', 'w') as file:
       file.write(str(k) + '\n')
       file.write(' '.join(map(str, counts_list)))

if __name__ == "__main__":

   main()

</syntaxhighlight>

 Explicatie 

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