Parcurgerea pe niveluri
Parcurgerile în adâncime coboară până la frunze înainte să treacă la alt copil. Uneori însă vrei arborele nivel cu nivel: întâi rădăcina, apoi copiii ei, apoi nepoții. Asta e parcurgerea în lățime (BFS), iar unealta ei este o coadă (deque), pe care o cunoști din modulul trecut.
Ideea: o coadă
Coada respectă regula „primul venit, primul servit”. Pui rădăcina în coadă; apoi, cât timp coada nu e goală, scoți un nod din față, îl procesezi și îi pui copiii la coadă. Copiii unui nivel ajung în coadă după toate nodurile nivelului curent, deci nodurile ies exact nivel cu nivel.
from collections import deque
class Nod:
def __init__(self, val, st=None, dr=None):
self.val = val Scrie pe_niveluri(radacina), care returnează lista nivelurilor (fiecare nivel este o listă de valori, de la stânga la dreapta), folosind o coadă deque și len(coada) la începutul fiecărui nivel, și vedere_dreapta(radacina), care returnează u…
- Pentru arborele gol returnează [].
- Cât timp coada nu e goală: scoate exact len(coada) noduri cu popleft(), adaugă valorile lor într-un nivel și pune copiii lor la coadă.
- Trebuie să apară: [[3], [9, 20], [15, 7]], [3, 20, 7], [[1], [2, 3], [4, 5]], [1, 3, 5], [] [].
Restul explicațiilor, editorul și verificarea automată se deblochează cu Arbori, grafuri și heap.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan