Diàmetre de l’arbre

Donat un arbre binari a, volem obtenir el seu diàmetre.

El diàmetre d’un arbre binari es defineix com el nombre d’arestes del
camí més llarg entre dos nodes qualsevol. No pot haver ni nodes repetits
ni arestes repetides en aquest camí. El diàmetre de l’arbre buit és 0.
És irrellevant el contingut (el valor) dels nodes, aquesta propietat és
una propietat exclusivament de l’estructura de l’arbre. Fixeu-vos que el
camí en qüestió no té per què passar per l’arrel.

Per exemple:

[image]

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

Paràmetres i retorn de la funció demanada

El paràmetre de la funció diametre(a) és una instància de la classe
ArbreBinari (que ja coneixem).

La funció diametre(a) ha de retornar dos coses: el diàmetre de l’arbre
(un nombre enter) i l’alçada de l’arbre (un nombre enter; nombre de
nodes entre l’arrel i alguna de les fulles més profundes, ambdós
inclosos). Recordeu que tant el diàmetre com l’alçada de l’arbre buit
són 0.

Entrada

L’entrada al programa serà el preordre de l’arbre binari, amb marca -1
per indicar els arbres buits (ja coneixem aquest format dels exercicis a
classe de laboratori). Fixem-nos que no ens importa què contenen els
nodes de l’arbre.

Vegeu els exemples del joc de proves públic.

Sortida

El programa ha d’escriure el diàmetre de l’arbre llegit.

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 ArbreBinari que hem treballat a
les classes de teoria i laboratori. Hem tret alguns mètodes que segur no
tenen cap utilitat per resoldre aquest problema. No caldrà que la vostra
solució faci cap import ni res. Tot el codi que us cal el teniu dins de
code.py.

Us fem retornar tant el diàmetre de l’arbre com l’alçada perquè aquesta
és tota la informació que necessiteu dels fills per conèixer el diàmetre
i l’alçada de l’arbre.

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

Informació del problema

Autoria: Jordi Delgado

Generació: 2026-04-01T05:09:34.610Z

© Jutge.org, 2006–2026.
https://jutge.org
