Arbre d'alçades X22410


Statement
 

pdf   zip   tar

html

Implementeu una funció RECURSIVA que, donat un arbre binari d’enters, retorna un nou arbre amb la mateixa estructura, i a on cada posició conté un número que és l’alçada del subarbre que penja d’aquella posició. Noteu que, si l’arbre és buit, llavors té alçada 0, i si l’arbre té un únic node (que serà arrel i fulla alhora), llavors té alçada 1. Aquesta és la capcelera:

// Pre:
// Post: Retorna un arbre d'enters amb la mateixa estructura que t,
//       i a on cada subarbre té com a arrel la seva alçada.
BinaryTree<int> treeOfHeights(BinaryTree<int> t);

Aquí tenim un exemple de paràmetre d’entrada de la funció i la corresponent sortida:

treeOfHeights(3(1(,5),3(2(1,7),))) => 4(2(,1),3(2(1,1),))

Fixeu-vos que l’enunciat d’aquest exercici ja ofereix uns fitxers que haureu d’utilitzar per a compilar: Makefile, program.cpp, BinaryTree.hpp, treeOfHeights.hpp. Us falta crear el fitxer treeOfHeights.cpp amb els corresponents includes i implementar-hi la funció anterior. Quan pugeu la vostra solució al jutge, només cal que pugeu un tar construït així: 

tar cf solution.tar treeOfHeights.cpp

Entrada

L’entrada té un nombre arbitrari de casos. Cada cas consisteix en una línia amb un string describint un arbre binari d’enters. Fixeu-vos en que el programa que us oferim ja s’encarrega de llegir aquestes entrades. Només cal que implementeu la funció abans esmentada.

Sortida

Per a cada cas, la sortida conté el corresponent arbre d’alçades. Fixeu-vos en que el programa que us oferim ja s’encarrega d’escriure aquesta sortida. Només cal que implementeu la funció abans esmentada.

Observació

La vostra funció i subfuncions que creeu han de treballar només amb arbres. Heu de trobar una solució RECURSIVA del problema. En les crides recursives, incloeu la hipòtesi d’inducció, és a dir una explicació del que es cumpleix després de la crida, i també la funció de fita/decreixement o una justificació de perquè la funció recursiva acaba.

Molt possiblement, una solució directa serà lenta, i necessitareu crear alguna funció recursiva auxiliar per a produïr una solució més eficient capaç de superar tots els jocs de proves.

Public test cases

  • Input

    7(2(5,3(4,5)),1)
6(7(8,7),8(4,6))
2(4(7(5,3),),2(8,7(2(7,),)))
3(7(5,1),3(5,4))
7(3,4)
6(,5(7,2))
2
4(6(1,3),)
4(,8(8(1,5),4(7,)))
4

    Output

    4(3(1,2(1,1)),1)
3(2(1,1),2(1,1))
5(3(2(1,1),),4(1,3(2(1,),)))
3(2(1,1),2(1,1))
2(1,1)
3(,2(1,1))
1
3(2(1,1),)
4(,3(2(1,1),2(1,)))
1

  • Input

    0(55(29(-47(-15,98),),-18(86(-59(60(29(,-38),30),-13(-80,-29)),62(-21,2(12(-28,-20),-67(-58,-79)))),-56(-5(-100(-37(7,-70),-18(,-82)),-34(30,94(-46,))),96(,51(63(41,-88),))))),-8)
75(-46(-53(-48,-53),98(,61)),-49)
67(25,-50)
9(-87,25(95,))
15(-92(-47(70,),-87),)
4(-1(27,-35),)
78(86(-5(,68),),46(88(-59,-9(68,83)),79(89(-93,-72),-31(-76,-91))))
-25(93(76(4,-8),-51(-22(-3,21),31(-34,32))),-95(-40(,53),93(,-81(16(-61,13(89,)),-7(-20,37)))))
94(37(,6),72(-90(,24(,-38(55(-65,22),46))),38(69(22(-65,-12),-54(49(78,-10),-3)),52(56,39(80(,24(-48,)),8(68(-38(,85),27(76,-13)),33(74,32)))))))
58
-20(82,81(-19,37))
97(-45(53(87(-96(-16(-35,97(,-23)),65(97,52(56,))),59(20(55(77,-30),),61)),),-26(98(,15),48(,-71(-22,)))),90(-99(88(,-4(-79(52(-16,),-27(,-80)),-36(-94,83))),),57(25(66(42(-49(-6,26),),57(-96,-75)),96(-15(,-46(,27)),1(91,44))),40(,-44))))
-6(-10(,25(80,6(57,47))),-60(80,87))
40(-71(4(-17(90(,-4(,-57)),-67(,-87)),100),20(14(-28,80),-11(-30,-2))),70(80,))
-14(-95(-31(41(-30(59(-71(27,-4),-75(,-92)),),59),-42),13(31(,-79),-24(62(52(80,-94(,-60)),26(,39)),8(45(,53),-73(11,26))))),60(-2(-2(-73,78(-82,10(-71(,-45(-19,-16)),-28))),-96(-12(88(83(-6,-52(7,-29)),-80),-39(33(11(,35),12),36(11(,13(53(-94,),-67)),30(-4,57)))),41(,66(91,97)))),-64(,93(49,))))
8(54(11(-99(67(7,),),-47(-10,-18)),82(9,-9)),43(16,-56))
-69(-15(25(57(38(-54,-13),80),-5),39(,-5(-28(-34,),74(-30,)))),67(41(4,),-19(72,)))
-53(19,35(9(29(-5,87),-60(21(-7,-16),)),62(-37(90(47,28),-35(91,40)),60)))
40(-49(-36,-47(51(-22(-7(-67(74(33,-100),18),-91(13,)),-69(73(-3,53(5,-65)),)),74(-100,-88)),42(-69(-100,),-35(27(28(-70(40(48,),-46(-26(-40,),)),14(,13)),-51(7,-40)),40(-53(0(57,83),7(-47(18,55),18(-58,))),-48))))),97(88(69(-81(,-9(49(21(33(67(61,-38),),-74),77(22(28,-43(-93,88)),-43(55(-73,-25),))),)),55(-52,)),-38(100(79(3,42(-63(,41(,-1)),50)),-90(0(-40(-11,-93(99,)),28(-95(-55,),-28)),)),-38(,-61(-71(40(,-71),),-66(12(-33,-73),))))),18(-8(100(-98(,1(-28(70(35(7,-25),-61),),99)),13(83(19(-91,-38),76(27,-79)),55)),49(-86(-58(60,8),-34),17(-27(52(82,),-22(-15,)),-99(31(-28(98,-23),-55(59(93,),)),-65(-15(5(28,-79),95(60,93)),-82(-91(20,),-1(61,))))))),-53(69(82,),4(-50(,-55(90(-86,-51),-72(-97(5(55,),),))),0(-31(57(22(-94,),48(-71(,57),-93(3,))),-63(-79(96,-20),-18(-27,-99))),29(51,38(70,))))))))
-9(-64(16,),49(-79,74))

    Output

    8(7(3(2(1,1),),6(5(4(3(2(,1),1),2(1,1)),4(1,3(2(1,1),2(1,1)))),5(4(3(2(1,1),2(,1)),3(1,2(1,))),4(,3(2(1,1),))))),1)
4(3(2(1,1),2(,1)),1)
2(1,1)
3(1,2(1,))
4(3(2(1,),1),)
3(2(1,1),)
5(3(2(,1),),4(3(1,2(1,1)),3(2(1,1),2(1,1))))
7(4(2(1,1),3(2(1,1),2(1,1))),6(2(,1),5(,4(3(1,2(1,)),2(1,1)))))
9(2(,1),8(5(,4(,3(2(1,1),1))),7(4(2(1,1),3(2(1,1),1)),6(1,5(3(,2(1,)),4(3(2(,1),2(1,1)),2(1,1)))))))
1
3(1,2(1,1))
8(7(6(5(4(3(1,2(,1)),3(1,2(1,))),4(3(2(1,1),),1)),),4(2(,1),3(,2(1,)))),7(6(5(,4(3(2(1,),2(,1)),2(1,1))),),6(5(4(3(2(1,1),),2(1,1)),4(3(,2(,1)),2(1,1))),2(,1))))
5(4(,3(1,2(1,1))),2(1,1))
7(6(5(4(3(,2(,1)),2(,1)),1),3(2(1,1),2(1,1))),2(1,))
11(7(6(5(4(3(2(1,1),2(,1)),),1),1),6(2(,1),5(4(3(1,2(,1)),2(,1)),3(2(,1),2(1,1))))),10(9(6(1,5(1,4(3(,2(1,1)),1))),8(7(4(3(1,2(1,1)),1),6(3(2(,1),1),5(4(,3(2(1,),1)),2(1,1)))),3(,2(1,1)))),3(,2(1,))))
6(5(4(3(2(1,),),2(1,1)),2(1,1)),2(1,1))
6(5(4(3(2(1,1),1),1),4(,3(2(1,),2(1,)))),3(2(1,),2(1,)))
6(1,5(4(2(1,1),3(2(1,1),)),4(3(2(1,1),2(1,1)),1)))
11(10(1,9(6(5(4(3(2(1,1),1),2(1,)),4(3(1,2(1,1)),)),2(1,1)),8(2(1,),7(6(5(4(2(1,),3(2(1,),)),2(,1)),2(1,1)),5(4(2(1,1),3(2(1,1),2(1,))),1))))),10(9(8(7(,6(5(4(3(2(1,1),),1),4(3(1,2(1,1)),3(2(1,1),))),)),2(1,)),7(6(5(1,4(3(,2(,1)),1)),5(4(3(1,2(1,)),3(2(1,),1)),)),5(,4(3(2(,1),),3(2(1,1),))))),9(8(7(6(,5(4(3(2(1,1),1),),1)),4(3(2(1,1),2(1,1)),1)),7(3(2(1,1),1),6(3(2(1,),2(1,)),5(4(2(1,1),3(2(1,),)),4(3(2(1,1),2(1,1)),3(2(1,),2(1,))))))),8(2(1,),7(6(,5(2(1,1),4(3(2(1,),),))),6(5(4(2(1,),3(2(,1),2(1,))),3(2(1,1),2(1,1))),3(1,2(1,))))))))
3(2(1,),2(1,1))
    • Information
    Author
    PRO1
    Language
    Catalan
    Official solutions
    Make
    User solutions
    Make