Arbre de mides X61092


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é el nombre total de nodes del subarbre que penja d’aquella mateixa posició a l’arbre inicial. 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 valor a l'arrel el nombre de nodes
//       del corresponent subarbre a t.
BinaryTree<int> treeOfSizes(BinaryTree<int> t);

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

treeOfSums(3(1(,5),3(2(1,7),))) => 7(2(,1),4(3(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, treeOfSizes.hpp. Us falta crear el fitxer treeOfSizes.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 treeOfSizes.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 de mides. 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

    7(5(1,3(1,1)),1)
7(3(1,1),3(1,1))
10(4(3(1,1),),5(1,3(2(1,),)))
7(3(1,1),3(1,1))
3(1,1)
4(,3(1,1))
1
4(3(1,1),)
7(,6(3(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

    43(41(4(3(1,1),),36(18(8(4(2(,1),1),3(1,1)),9(1,7(3(1,1),3(1,1)))),17(11(6(3(1,1),2(,1)),4(1,2(1,))),5(,4(3(1,1),))))),1)
8(6(3(1,1),2(,1)),1)
3(1,1)
4(1,2(1,))
5(4(2(1,),1),)
4(3(1,1),)
17(3(2(,1),),13(5(1,3(1,1)),7(3(1,1),3(1,1))))
24(11(3(1,1),7(3(1,1),3(1,1))),12(2(,1),9(,8(4(1,2(1,)),3(1,1)))))
37(2(,1),34(7(,6(,5(3(1,1),1))),26(9(3(1,1),5(3(1,1),1)),16(1,14(3(,2(1,)),10(6(2(,1),3(1,1)),3(1,1)))))))
1
5(1,3(1,1))
56(24(17(16(9(4(1,2(,1)),4(1,2(1,))),6(4(3(1,1),),1)),),6(2(,1),3(,2(1,)))),31(11(10(,9(5(2(1,),2(,1)),3(1,1))),),19(16(8(4(3(1,1),),3(1,1)),7(3(,2(,1)),3(1,1))),2(,1))))
10(6(,5(1,3(1,1))),3(1,1))
19(16(8(6(3(,2(,1)),2(,1)),1),7(3(1,1),3(1,1))),2(1,))
72(29(11(9(7(6(3(1,1),2(,1)),),1),1),17(2(,1),14(7(4(1,2(,1)),2(,1)),6(2(,1),3(1,1))))),42(38(10(1,8(1,6(4(,3(1,1)),1))),27(22(7(5(1,3(1,1)),1),14(4(2(,1),1),9(5(,4(2(1,),1)),3(1,1)))),4(,3(1,1)))),3(,2(1,))))
15(11(7(3(2(1,),),3(1,1)),3(1,1)),3(1,1))
20(14(7(5(3(1,1),1),1),6(,5(2(1,),2(1,)))),5(2(1,),2(1,)))
20(1,18(8(3(1,1),4(3(1,1),)),9(7(3(1,1),3(1,1)),1)))
192(51(1,49(19(15(8(5(3(1,1),1),2(1,)),6(5(1,3(1,1)),)),3(1,1)),29(2(1,),26(13(9(6(2(1,),3(2(1,),)),2(,1)),3(1,1)),12(10(3(1,1),6(3(1,1),2(1,))),1))))),140(51(22(19(,18(17(6(4(3(1,1),),1),10(5(1,3(1,1)),4(3(1,1),))),)),2(1,)),28(18(7(1,5(3(,2(,1)),1)),10(9(4(1,2(1,)),4(2(1,),1)),)),9(,8(3(2(,1),),4(3(1,1),))))),88(53(19(9(,8(6(5(3(1,1),1),),1)),9(7(3(1,1),3(1,1)),1)),33(5(3(1,1),1),27(5(2(1,),2(1,)),21(7(3(1,1),3(2(1,),)),13(7(3(1,1),3(1,1)),5(2(1,),2(1,))))))),34(2(1,),31(9(,8(3(1,1),4(3(2(1,),),))),21(16(8(2(1,),5(2(,1),2(1,))),7(3(1,1),3(1,1))),4(1,2(1,))))))))
6(2(1,),3(1,1))
    • Information
    Author
    PRO1
    Language
    Catalan
    Official solutions
    Make
    User solutions
    Make