Diàmetre de l'arbre S50568
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:
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.
Input
0 0 0 -1 -1 0 -1 -1 0 0 -1 -1 0 -1 -1
Output
4
Input
0 0 0 -1 -1 0 -1 -1 0 -1 -1
Output
3
Input
0 0 -1 -1 -1
Output
1
Input
0 0 0 -1 -1 0 -1 -1 0 0 -1 -1 0 -1 -1
Output
4
Input
0 -1 -1
Output
0
Input
0 0 -1 -1 0 -1 -1
Output
2
Input
0 -1 0 0 0 -1 -1 -1 0 -1 0 -1 -1
Output
4
- Author
- Jordi Delgado
- Language
- Catalan
- Translator
- Jordi Delgado
- Original language
- Spanish
- Other languages
- Spanish
- Official solutions
- Python
- User solutions
- Python