Oros Ioana Diana at 14:25, 18 May 2024

2024-05-18T14:25:19Z

← Older revision		Revision as of 14:25, 18 May 2024
Line 6:		Line 6:

	= Date de ieșire =		= Date de ieșire =
	Fișierul de ieșire <code>nivelebinOUT.txt</code> va conține pe prima linie numărul <code>k</code>, iar pe a doua linie <code>k+1</code> numere naturale separate prin exact un spațiu, al <code>i</code>-lea număr reprezentând numărul de noduri situate pe nivelul <code>i-1</code> din arbore.		Fișierul de ieșire <code>nivelebinOUT.txt</code> va conține pe prima linie numărul <code>k</code>, iar pe a doua linie <code>k+1</code> numere naturale separate prin exact un spațiu, al <code>i</code>-lea număr reprezentând numărul de noduri situate pe nivelul <code>i-1</code> din arbore. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

	= Restricții și precizări =		= Restricții și precizări =

Oros Ioana Diana at 14:23, 18 May 2024

2024-05-18T14:23:44Z

Show changes

Oros Ioana Diana: Pagină nouă: == 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...

2024-01-08T20:16:56Z

Pagină nouă: == 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...

New page

== 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
<br>
== 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
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#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.
<br>
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

0677 - Nivele Bin - Revision history

Oros Ioana Diana at 14:25, 18 May 2024

Oros Ioana Diana at 14:23, 18 May 2024