Parcurgerile în adâncime ale unui arbore
Scrie recursiv preordine(radacina), inordine(radacina) și postordine(radacina), fiecare returnând lista valorilor în ordinea respectivă. Pentru arborele gol returnează []. Clasa Nod și construieste sunt deja scrise.
- Cazul de bază:
if radacina is None: return []. - Combină
[radacina.val]cu rezultatele pentruradacina.stșiradacina.dr, în ordinea potrivită. - Trebuie să apară:
[1, 2, 4, 5, 3, 6],[4, 2, 5, 1, 3, 6],[4, 5, 2, 6, 3, 1],[] [7].
[radacina.val].from collections import deque
class Nod:
def __init__(self, val, st=None, dr=None):
self.val = val
self.st = st
self.dr = dr
def construieste(lista):
"""Creează arborele pe niveluri; None = lipsește copilul."""
if not lista or lista[0] is None:
return None
radacina = Nod(lista[0])
coada = deque([radacina])
i = 1
while coada and i < len(lista):
nod = coada.popleft()
if i < len(lista) and lista[i] is not None:
nod.st = Nod(lista[i])
coada.append(nod.st)
i += 1
if i < len(lista) and lista[i] is not None:
nod.dr = Nod(lista[i])
coada.append(nod.dr)
i += 1
return radacina
def preordine(radacina):
if radacina is None:
return []
return [radacina.val] + preordine(radacina.st) + preordine(radacina.dr)
def inordine(radacina):
if radacina is None:
return []
return inordine(radacina.st) + [radacina.val] + inordine(radacina.dr)
def postordine(radacina):
if radacina is None:
return []
return postordine(radacina.st) + postordine(radacina.dr) + [radacina.val]
arbore = construieste([1, 2, 3, 4, 5, None, 6])
print(preordine(arbore))
print(inordine(arbore))
print(postordine(arbore))
print(preordine(None), inordine(construieste([7])))


