L'Arbre Escorat (2) U15608

Donat un arbre (general) de naturals, el seu pes és la suma dels valors en els seus nodes i la seva mida és el nombre de nodes que té.

Escorar un arbre és transformar-lo de manera que, per a tots els seus nodes, els fills estiguin ordenats creixentment per pes, d’esquerra a dreta. En cas que dos fills pesin el mateix, els ordenarem d’acord a la seva mida, també creixentment.

Noteu que a l’arbre hi haurà els mateixos nodes abans i després d’escorar, però col·locats de manera diferent, i també hi ha els mateixos camins abans i després però disposats de manera diferent.

Us demanem, doncs, que feu una funció escorar(a) i l’afegiu al fitxer code.py tal com s’especifica a les Observacions.

Paràmetres i retorn

El paràmetre de la funció escorar(a) és una instància de la classe Arbre

Els valor en cada node de l’arbre és un nombre enter positiu.

La funció escorar(a) ha de retornar tres coses: el pes de l’arbre (un nombre enter), la mida de l’arbre (un nombre enter) i l’arbre escorat (instància d’Arbre) (en aquest ordre!).

Entrada

L’entrada al programa serà la descripció d’un arbre en preordre, en el que al valor de cada node li segueix el seu nombre de fills.

Vegeu els exemples del joc de proves públic.

Sortida

El programa ha d’escriure el preordre i el postordre de l’arbre escorat, amb els valors dels nodes separat per ’,’. El preordre i el postordre han d’estar en línies separades

Vegeu els exemples del joc de proves públic.

Observacions

Heu de baixar-vos el fitxer code.py (icona de la serp). Aquest fitxer és un programa amb tot el que cal per executar els jocs de prova públics. Només falta, clar, la funció que us demana l’enunciat. Aquest fitxer l’heu de completar amb el codi que falta, i això, tot, és el que heu d’enviar al Jutge com a solució.

Dins el fitxer code.py teniu la classe Arbre. Enteneu-la abans de procedir. És molt senzilla. No caldrà que la vostra solució faci cap import ni res. Tot el codi que us cal el teniu dins de code.py.

Cal considerar que la classe Arbre no té definit l’operador < per tant no es poden comparar les instàncies d’Arbre. Si feu servir sort, recordeu que hi ha un paràmetre key que us permet extreure la informació que interessa comparar d’allò que esteu ordenant.

L’eficiència i la qualitat de la solució es tindran en compte a la correcció manual.