El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Recorreguts d'Arbres

Següent ►
►

Ja saps construir arbres binaris; ara toca visitar-los amb mètode. En una llista només hi ha una manera raonable de recórrer els elements (del primer a l'últim); en un arbre, en canvi, a cada node cal decidir: processo el node abans de baixar, entre els seus dos fills, o després de pujar? Cada resposta defineix un recorregut amb nom propi — preordre, inordre i postordre — i s'hi suma el recorregut per nivells, que no baixa en profunditat sinó que escombra l'arbre pis a pis amb una cua. Triar el recorregut correcte és el que diferencia "tocar tots els nodes" de "resoldre el problema": a TaskFlow, exportar la jerarquia, calcular hores acumulades i pintar l'organigrama per nivells usen tres recorreguts diferents. A més, aquesta lliçó reuneix vells amics: la recursió i la pila explícita del mòdul 3, i la cua del mòdul 4.

Contingut

  1. El problema: en quin ordre visito els nodes?
  2. Preordre, inordre i postordre: els tres recorreguts en profunditat
  3. Traça detallada: els tres recorreguts sobre el mateix arbre
  4. Recorregut per nivells: la cua entra en escena
  5. Versions iteratives amb pila explícita
  6. Quan usar cada recorregut (amb TaskFlow com a guia)

El problema: en quin ordre visito els nodes?

Recórrer un arbre és visitar cada node exactament una vegada. Amb la definició recursiva de l'arbre binari (un node + subarbre esquerre + subarbre dret), recórrer-lo exigeix fer tres coses: processar el Node, recórrer el subarbre Esquerre i recórrer el subarbre Dret. L'únic que distingeix els recorreguts en profunditat és el moment en què es processa el node (mantindrem sempre esquerra abans que dreta):

Recorregut Ordre Mnemotècnia
Preordre N, E, D El node abans que els seus fills
Inordre E, N, D El node entre els seus fills
Postordre E, D, N El node després dels seus fills

Els tres són recorreguts en profunditat (DFS, depth-first): s'enfonsen per una branca fins al fons abans de tocar la següent. El quart recorregut, per nivells (BFS, breadth-first), trenca el motlle: visita tots els nodes de profunditat 0, després tots els de profunditat 1, etc. Avançament per al mòdul 7: DFS i BFS són en realitat estratègies generals d'exploració de grafs; aquí les coneixem en la seva versió domèstica, sobre arbres, on són més simples perquè no hi ha cicles.

Preordre, inordre i postordre: els tres recorreguts en profunditat

Les tres funcions són gairebé idèntiques — només es mou una línia. Farem servir aquest arbre durant tota la lliçó:

graph TD
    A((10)) --> B((6))
    A --> C((15))
    B --> D((3))
    B --> E((8))
    C --> F((12))
    C --> G((20))
class NodeBinari:
    def __init__(self, valor):
        self.valor = valor
        self.esquerre = None
        self.dret = None

arrel = NodeBinari(10)
arrel.esquerre = NodeBinari(6)
arrel.dret = NodeBinari(15)
arrel.esquerre.esquerre = NodeBinari(3)
arrel.esquerre.dret = NodeBinari(8)
arrel.dret.esquerre = NodeBinari(12)
arrel.dret.dret = NodeBinari(20)

def preordre(node, resultat):
    if node is None:
        return
    resultat.append(node.valor)           # N primer...
    preordre(node.esquerre, resultat)     # ...després E...
    preordre(node.dret, resultat)         # ...després D

def inordre(node, resultat):
    if node is None:
        return
    inordre(node.esquerre, resultat)      # E primer...
    resultat.append(node.valor)           # ...N al mig...
    inordre(node.dret, resultat)          # ...després D

def postordre(node, resultat):
    if node is None:
        return
    postordre(node.esquerre, resultat)    # E...
    postordre(node.dret, resultat)        # ...D...
    resultat.append(node.valor)           # ...i N al final

for f in (preordre, inordre, postordre):
    r = []
    f(arrel, r)
    print(f.__name__, r)
# preordre  [10, 6, 3, 8, 15, 12, 20]
# inordre   [3, 6, 8, 10, 12, 15, 20]
# postordre [3, 8, 6, 12, 20, 15, 10]

Tres observacions abans de la traça:

  • Els tres costen O(n) en temps (cada node es visita una vegada) i O(altura) en memòria — la pila de crides del mòdul 3 arriba a apilar tantes crides com profunditat tingui la branca més fonda.
  • En preordre, l'arrel surt la primera; en postordre, l'última. Aquest detall serà clau a l'exercici de reconstrucció de 06-08.
  • Mira la sortida d'inordre: [3, 6, 8, 10, 12, 15, 20]. Ordenada. No és casualitat: aquest arbre compleix (espòiler) la propietat que definirà la propera lliçó, i l'inordre d'un arbre així sempre surt en ordre ascendent. És l'anunci formal: a 06-04 això passarà de curiositat a teorema i eina.

Traça detallada: els tres recorreguts sobre el mateix arbre

Seguim el preordre pas a pas, amb la pila de crides a la vista (sagnia = profunditat de la crida):

preordre(10): afegeix 10                      → [10]
  preordre(6): afegeix 6                      → [10, 6]
    preordre(3): afegeix 3                    → [10, 6, 3]
      preordre(None) x2: return
    preordre(8): afegeix 8                    → [10, 6, 3, 8]
      preordre(None) x2: return
  preordre(15): afegeix 15                    → [10, 6, 3, 8, 15]
    preordre(12): afegeix 12                  → [10, 6, 3, 8, 15, 12]
    preordre(20): afegeix 20                  → [10, 6, 3, 8, 15, 12, 20]

Cada crida afegeix el seu valor tot just entrar i després delega. Ara l'inordre sobre el subarbre esquerre (el patró es repeteix a dalt):

inordre(10)
  inordre(6)
    inordre(3)
      inordre(None): return   ← el 3 no té fill esquerre
      afegeix 3                                → [3]
      inordre(None): return
    afegeix 6                 ← només després d'esgotar TOT el seu subarbre esquerre → [3, 6]
    inordre(8)
      afegeix 8                                → [3, 6, 8]
  afegeix 10                  ← el 10 espera que acabi la seva branca esquerra sencera → [3, 6, 8, 10]
  inordre(15) ...                              → [3, 6, 8, 10, 12, 15, 20]

I el postordre: cada node espera que acabin els seus dos subarbres — per això el 6 surt després del 3 i el 8, i l'arrel 10 surt l'última de totes. Un truc visual per autocomprovar-te sense traçar:

graph TD
    A(("10 ③")) --> B(("6 ②"))
    A --> C(("15 ⑥"))
    B --> D(("3 ①"))
    B --> E(("8 ④"))
    C --> F(("12 ⑤"))
    C --> G(("20 ⑦"))

Recorre el contorn de l'arbre partint de l'arrel per l'esquerra: en preordre anotes cada node el primer cop que el toques per la seva esquerra; en inordre, quan el passes per sota (els números del diagrama són l'ordre inordre); en postordre, l'últim cop que el toques, per la seva dreta. Amb un llapis i 20 segons verifiques qualsevol recorregut.

Recorregut per nivells: la cua entra en escena

Per visitar per nivells (10, després 6 i 15, després 3-8-12-20) la recursió no ajuda: la profunditat no és l'ordre que volem. L'eina correcta la vas construir al mòdul 4 — una cua FIFO. L'algorisme: encua l'arrel; mentre la cua no estigui buida, desencua un node, processa'l i encua els seus fills. Els fills, en entrar per darrere, esperen el seu torn que acabi el nivell actual.

from collections import deque      # el deque del mòdul 4: O(1) per tots dos extrems

def per_nivells(arrel):
    if arrel is None:
        return []
    resultat = []
    cua = deque([arrel])
    while cua:
        node = cua.popleft()                # surt el més antic (FIFO)
        resultat.append(node.valor)
        if node.esquerre:
            cua.append(node.esquerre)       # els fills, al final de la cua
        if node.dret:
            cua.append(node.dret)
    return resultat

print(per_nivells(arrel))   # [10, 6, 15, 3, 8, 12, 20]

Traça de l'estat de la cua (esquerra = el proper a sortir):

Pas Surt Entra Cua després Resultat
1 10 6, 15 [6, 15] [10]
2 6 3, 8 [15, 3, 8] [10, 6]
3 15 12, 20 [3, 8, 12, 20] [10, 6, 15]
4-7 3, 8, 12, 20 — [] [10, 6, 15, 3, 8, 12, 20]

I aquí es tanca un cercle pendent: l'exercici binaris_fins(n) del mòdul 4 ("1, 10, 11, 100, 101...") feia exactament això — cada cadena binària s encuava els seus "fills" s+'0' i s+'1'; estaves recorrent per nivells l'arbre binari perfecte de totes les cadenes binàries, sense haver vist encara cap arbre. Aquest recorregut és un BFS amb totes les lletres; al mòdul 7 el generalitzarem a grafs, on necessitarà el conjunt visitats que vam anticipar a 05-04 (en un arbre no cal: sense cicles i amb un sol pare, és impossible encuar dues vegades el mateix node). Cost: O(n) en temps; en memòria, O(amplada màxima) — en un arbre perfecte, l'últim nivell té ≈ n/2 nodes, així que pot ser O(n).

Versions iteratives amb pila explícita

Al mòdul 3 vas aprendre (amb les subtasques niades i el seu RecursionError) que tota recursió es pot convertir en iteració gestionant tu la pila. Amb arbres molt profunds — un arbre degenerat de 10 000 nodes supera el límit de recursió de Python — aquesta conversió passa d'elegància a necessitat. Preordre iteratiu:

def preordre_iteratiu(arrel):
    if arrel is None:
        return []
    resultat = []
    pila = [arrel]                     # una llista de Python com a pila (mòdul 3)
    while pila:
        node = pila.pop()              # LIFO: surt l'últim apilat
        resultat.append(node.valor)
        if node.dret:                  # el dret PRIMER!...
            pila.append(node.dret)
        if node.esquerre:              # ...perquè l'esquerre quedi a sobre
            pila.append(node.esquerre)
    return resultat

print(preordre_iteratiu(arrel))   # [10, 6, 3, 8, 15, 12, 20] — igual que el recursiu

El detall contraintuïtiu: s'apila el fill dret abans que l'esquerre, perquè la pila inverteix — l'últim a entrar és el primer a sortir, i volem processar abans l'esquerre. Compara amb per_nivells: el mateix esquelet, canviant la cua per una pila. Aquesta simetria (cua → per nivells/BFS; pila → en profunditat/DFS) és una de les idees més belles del curs i reapareixerà literal al mòdul 7.

L'inordre iteratiu és més subtil: no pots processar un node en treure'l sense més, perquè el seu torn arriba després de tot el seu subarbre esquerre. La tècnica: lliscar fins al fons esquerre apilant el camí, i en retrocedir, processar i saltar al subarbre dret.

def inordre_iteratiu(arrel):
    resultat = []
    pila = []
    node = arrel
    while pila or node is not None:
        while node is not None:        # 1) baixar per l'esquerra apilant el camí
            pila.append(node)
            node = node.esquerre
        node = pila.pop()              # 2) sense més esquerra: toca aquest node
        resultat.append(node.valor)
        node = node.dret               # 3) i ara el seu subarbre dret
    return resultat

print(inordre_iteratiu(arrel))   # [3, 6, 8, 10, 12, 15, 20]

La pila reprodueix a mà el que la pila de crides feia sola: recordar els ancestres pendents de processar. (El postordre iteratiu és encara més enrevessat — dues piles o marcatge de visitats — i rarament es necessita; amb saber que existeix, n'hi ha prou.)

Quan usar cada recorregut (amb TaskFlow com a guia)

La regla general: pregunta't què necessita estar fet abans de processar un node.

Necessites... Recorregut Per què A TaskFlow
Processar el pare abans que els fills (crear, copiar, serialitzar) Preordre El pare ha d'existir abans de penjar-hi fills Exportar l'arbre de projectes amb indentació
Els valors en ordre ascendent (en un ABC) Inordre Esquerra < node < dreta (ho provarem a 06-04) Llistat de tasques ordenat per id
Els resultats dels fills abans de processar el pare (agregar, alliberar, esborrar) Postordre El pare resumeix/depèn dels seus subarbres Hores acumulades per projecte
Processar per proximitat a l'arrel Per nivells La cua garanteix l'ordre per profunditat Vista "projectes → categories → tasques" pis a pis

Un altre exemple clàssic de postordre: esborrar un arbre en llenguatges amb gestió manual de memòria — cal alliberar els fills abans que el pare per no perdre'n les referències. I els arbres d'expressions aritmètiques donen els tres: preordre = notació prefixa, inordre = la notació habitual amb parèntesis, postordre = la notació polonesa inversa que vam avaluar amb una pila al mòdul 3.

Dos dels usos de TaskFlow, en codi. El preordre que exporta la jerarquia (és la funció mostrar de 06-01! — processava el node i després els fills: era un preordre sense saber-ho) i el postordre que acumula hores:

def hores_acumulades(node):
    """Hores del subarbre: les pròpies més les de tots els descendents.
    Cada node porta a valor un dict amb almenys {'titol', 'hores'}."""
    if node is None:
        return 0
    total_fills = sum(hores_acumulades(f) for f in [node.esquerre, node.dret])
    return node.valor["hores"] + total_fills     # el pare, DESPRÉS dels seus fills

No hi ha manera de saber quant costa un projecte sense sumar-ne abans les parts: la naturalesa del problema imposa postordre. (A 06-08 ho farem en gran, amb pressupostos sobre l'arbre genèric.)

Errors Comuns i Consells

  • Apilar el fill esquerre primer al preordre iteratiu. La pila inverteix l'ordre: dret primer, esquerre després. És el despiste número u; si el teu preordre iteratiu surt "en mirall", és això.
  • Usar una pila per al recorregut per nivells (o una cua per al DFS). L'estructura auxiliar és el recorregut: pila → profunditat, cua → nivells. Si ho barreges, obtens l'altre recorregut sense voler.
  • Processar el node en el moment equivocat. Calcular totals acumulats en preordre obliga a contorsions; en postordre surten sols. Abans de programar, decideix quina informació ha de fluir: de pares a fills (preordre, com el paràmetre profunditat) o de fills a pares (postordre, com les hores).
  • Confiar en la recursió amb arbres de profunditat desconeguda. Un arbre degenerat amb milers de nodes rebenta la pila de crides (RecursionError, mòdul 3). Per a dades d'origen extern, la versió iterativa és la defensiva.
  • Consell: memoritza les sortides d'aquest arbre d'exemple (pre: arrel primer; in: ordenat; post: arrel al final). Tenir un cas resolt al cap et permet validar qualsevol implementació en segons.

Exercicis

Exercici 1: per nivells, amb els nivells separats

Modifica per_nivells perquè retorni una llista de llistes, una per nivell: [[10], [6, 15], [3, 8, 12, 20]]. Pista: abans de buidar cada nivell, len(cua) et diu quants nodes el formen.

Exercici 2: profunditat màxima sense recursió

Usant el resultat de l'exercici 1 (o directament una cua), escriu altura_iterativa(arrel) que calculi l'altura de l'arbre sense recursió. Per a l'arbre de la lliçó ha de retornar 2.

Exercici 3: exportar TaskFlow en preordre iteratiu

Sobre l'arbre genèric (NodeArbre de 06-01, amb llista fills), escriu exportar(arrel) iteratiu amb pila explícita que retorni les línies indentades de la jerarquia (com mostrar de 06-01, però sense recursió i retornant una llista). Pista: apila parelles (node, profunditat), i apila els fills en ordre invers per conservar-ne l'ordre natural.

Solucions

Solució 1

def nivells_separats(arrel):
    if arrel is None:
        return []
    resultat = []
    cua = deque([arrel])
    while cua:
        mida_nivell = len(cua)              # tots els que hi ha ARA són d'aquest nivell
        nivell = []
        for _ in range(mida_nivell):
            node = cua.popleft()
            nivell.append(node.valor)
            if node.esquerre:
                cua.append(node.esquerre)
            if node.dret:
                cua.append(node.dret)
        resultat.append(nivell)
    return resultat

print(nivells_separats(arrel))   # [[10], [6, 15], [3, 8, 12, 20]]

Comentari: la clau és la instantània mida_nivell = len(cua) — en començar cada volta del while, la cua conté exactament un nivell complet, i el for el consumeix mentre encua el següent. Sense la instantània, els fills acabats d'encuar es barrejarien amb el nivell en curs. Aquest patró "processar per tandes" és un clàssic d'entrevistes.

Solució 2

def altura_iterativa(arrel):
    return len(nivells_separats(arrel)) - 1

print(altura_iterativa(arrel))   # 2

Comentari: l'altura és el nombre de nivells menys 1 (l'arrel és el nivell 0), i de passada l'arbre buit retorna −1, consistent amb la convenció de 06-02. Sense recursió no hi ha RecursionError possible: aquesta versió aguanta l'arbre degenerat que tombaria la recursiva.

Solució 3

def exportar(arrel):
    if arrel is None:
        return []
    linies = []
    pila = [(arrel, 0)]                      # parella (node, profunditat)
    while pila:
        node, prof = pila.pop()
        if isinstance(node.valor, dict):
            etiqueta = f"[{node.valor['id']}] {node.valor['titol']}"
        else:
            etiqueta = node.valor
        linies.append("    " * prof + etiqueta)
        for fill in reversed(node.fills):    # invers: el primer queda a dalt
            pila.append((fill, prof + 1))
    return linies

Comentari: dues idees es combinen. Primera: com que no hi ha pila de crides que recordi la profunditat, hi viatgem amb ella a la tupla — l'equivalent manual del paràmetre profunditat de 06-01. Segona: reversed(node.fills) generalitza el truc "dret abans que esquerre" a n fills. El resultat és idèntic línia a línia al de mostrar, però immune al RecursionError: TaskFlow ja pot exportar jerarquies de qualsevol profunditat.

Conclusió

Ja domines les quatre maneres canòniques de visitar un arbre: preordre (el node primer — copiar, serialitzar, exportar), inordre (el node al mig — i aquella sortida ordenada el secret de la qual es revela a la propera lliçó), postordre (el node al final — agregar i alliberar de fills a pares) i per nivells (la cua del mòdul 4 escombrant pis a pis — el teu primer BFS, que al mòdul 7 saltarà als grafs). I saps baixar-los a terra amb pila explícita quan la profunditat amenaça la recursió. Amb l'estructura (06-02) i els recorreguts (06-03) a la mà, arriba el moment de la recompensa: afegir a l'arbre binari una regla de col·locació — menors a l'esquerra, majors a la dreta — i veure com, de cop, cercar costa O(altura), l'inordre regala les dades ordenades i les consultes per interval que el hash no sabia respondre ("prioritat entre 1 i 3") per fi tenen amo. És l'arbre binari de cerca, i és la propera lliçó.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats