Fill esquerre, germà dret (1) P32655

Fill esquerre, germà dret és el nom d’una coneguda bijecció entre els arbres generals i els arbres binaris no buits amb subarbre dret buit. Per passar de l’arbre general al binari, a cada node se li posa el primer fill (començant per l’esquerra) com a fill esquerre, i la resta de nodes es posen l’un rera l’altre com a fill dret del germà anterior.

(Per veure un exemple amb un arbre amb la mateixa forma que el primer arbre de l’exemple d’entrada-sortida, consulteu la versió pdf o ps d’aquest enunciat.)

Feu un programa que llegeixi la forma de diversos arbres generals, i que per a cadascun escrigui l’alçada de l’arbre binari corresponent.

Entrada

L’entrada comença amb m, el nombre d’arbres que cal tractar. Segueix la descripció dels m ‍arbres segons s’explica a l’exercici , amb dues excepcions: D’una banda, no es donen els valors, perquè el contingut dels nodes aquí no és important. De l’altra, tampoc no es dóna el nombre de nodes, ja que no cal guardar els arbres a cap vector per resoldre aquest exercici.

Sortida

Escriviu l’alçada de l’arbre binari corresponent a cada arbre donat.