Arbre de sumes X63359
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é la suma 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 arrel la suma dels nodes del corresponent subarbre a t. BinTree<int> treeOfSums(BinTree<int> t);
Aquí tenim un exemple de paràmetre d’entrada de la funció i la corresponent sortida:
treeOfSums( 3 ) => 22
| |
------- ------- ------- -------
| | | |
1 3 6 13
| | | |
---- ---- ---- ----
| | | |
5 2 5 10
| |
---- ---- ---- ----
| | | |
1 7 1 7
Fixeu-vos que l’enunciat d’aquest exercici ja ofereix uns fitxers que haureu d’utilitzar per a compilar: Makefile, program.cc, BinTree.hh, treeOfSums.hh. Us falta crear el fitxer treeOfSums.cc 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 treeOfSums.cc
Entrada
La primera linia de l’entrada descriu el format en el que es descriuen els arbres, o bé INLINEFORMAT o bé VISUALFORMAT. Després venen un nombre arbitrari de casos. Cada cas consisteix en una descripció d’un arbre 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 sumes. 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.
Input
VISUALFORMAT
7
|
---- ----
| |
2 1
|
---- ----
| |
5 3
|
---- ----
| |
4 5
6
|
------- -------
| |
7 8
| |
---- ---- ---- ----
| | | |
8 7 4 6
2
|
---- ----
| |
4 2
| |
---- ---- ----
| | |
7 8 7
| |
---- ---- ----
| | |
5 3 2
|
----
|
7
3
|
------- -------
| |
7 3
| |
---- ---- ---- ----
| | | |
5 1 5 4
7
|
---- ----
| |
3 4
6
|
----
|
5
|
---- ----
| |
7 2
2
4
|
----
|
6
|
---- ----
| |
1 3
4
|
----
|
8
|
------- -------
| |
8 4
| |
---- ---- ----
| | |
1 5 7
4
Output
27
|
---- ----
| |
19 1
|
---- ----
| |
5 12
|
---- ----
| |
4 5
46
|
------- -------
| |
22 18
| |
---- ---- ---- ----
| | | |
8 7 4 6
47
|
---- ----
| |
19 26
| |
---- ---- ----
| | |
15 8 16
| |
---- ---- ----
| | |
5 3 9
|
----
|
7
28
|
------- -------
| |
13 12
| |
---- ---- ---- ----
| | | |
5 1 5 4
14
|
---- ----
| |
3 4
20
|
----
|
14
|
---- ----
| |
7 2
2
14
|
----
|
10
|
---- ----
| |
1 3
37
|
----
|
33
|
------- -------
| |
14 11
| |
---- ---- ----
| | |
1 5 7
4
Input
INLINEFORMAT 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
-271(-263(65(36(-15,98),),-383(-211(-100(81(-9(,-38),30),-122(-80,-29)),-197(-21,-238(-36(-28,-20),-204(-58,-79)))),-154(-261(-300(-100(7,-70),-100(,-82)),44(30,48(-46,))),163(,67(16(41,-88),))))),-8) -15(-41(-154(-48,-53),159(,61)),-49) 42(25,-50) 42(-87,120(95,)) -141(-156(23(70,),-87),) -5(-9(27,-35),) 249(149(63(,68),),22(171(-59,142(68,83)),-195(-76(-93,-72),-198(-76,-91)))) 111(139(72(4,-8),-26(-4(-3,21),29(-34,32))),-3(13(,53),79(,-14(57(-61,102(89,)),10(-20,37))))) 830(43(,6),693(-46(,44(,20(12(-65,22),46))),667(74(-55(-65,-12),60(117(78,-10),-3)),555(56,447(56(,-24(-48,)),352(205(47(,85),90(76,-13)),139(74,32))))))) 58 161(82,99(-19,37)) 792(576(579(526(197(23(-35,74(,-23)),270(97,108(56,))),242(122(102(77,-30),),61)),),42(113(,15),-45(,-93(-22,)))),119(-212(-113(,-201(-150(36(-16,),-107(,-80)),-47(-94,83))),),241(188(-35(13(-29(-6,26),),-114(-96,-75)),198(-34(,-19(,27)),136(91,44))),-4(,-44)))) 306(205(,215(80,110(57,47))),107(80,87)) 124(-66(-38(-142(29(,-61(,-57)),-154(,-87)),100),43(66(-28,80),-43(-30,-2))),150(80,)) 21(-138(-159(-86(-186(-156(-48(27,-4),-167(,-92)),),59),-42),116(-48(,-79),151(105(-22(80,-154(,-60)),65(,39)),70(98(,53),-36(11,26))))),173(35(-248(-73,-173(-82,-169(-151(,-80(-19,-16)),-28))),285(86(11(3(-6,-74(7,-29)),-80),87(91(46(,35),12),35(-84(,-95(-41(-94,),-67)),83(-4,57)))),295(,254(91,97)))),78(,142(49,)))) 58(47(-89(-25(74(7,),),-75(-10,-18)),82(9,-9)),3(16,-56)) 225(129(128(108(-29(-54,-13),80),-5),16(,-23(-62(-34,),44(-30,)))),165(45(4,),53(72,))) 405(19,439(58(111(-5,87),-62(-2(-7,-16),)),346(224(165(47,28),96(91,40)),60))) -627(-536(-36,-451(-218(-155(-127(-42(7(33,-100),18),-78(13,)),-6(63(-3,-7(5,-65)),)),-114(-100,-88)),-186(-169(-100,),-59(-96(-39(-94(88(48,),-112(-66(-40,),)),27(,13)),-84(7,-40)),72(80(140(57,83),-7(26(18,55),-40(-58,))),-48))))),-131(-251(94(22(,103(112(70(123(90(61,-38),),-74),-7(2(28,-48(-93,88)),-86(-43(-73,-25),))),)),3(-52,)),-433(-34(151(3,69(-23(,40(,-1)),50)),-285(-195(-45(-11,6(99,)),-150(-150(-55,),-28)),)),-361(,-323(-102(-31(,-71),),-160(-94(-33,-73),))))),23(288(165(0(,98(-2(26(17(7,-25),-61),),99)),65(-3(-110(-91,-38),24(27,-79)),55)),131(-110(10(60,8),-34),192(70(134(82,),-37(-15,)),105(175(47(98,-23),97(152(93,),)),29(187(-46(28,-79),248(60,93)),-93(-71(20,),60(61,))))))),-283(151(82,),-381(-261(,-211(-47(-86,-51),-109(-37(60(55,),),))),-124(-312(-71(-72(-94,),-56(-14(,57),-90(3,))),-210(-3(96,-20),-144(-27,-99))),188(51,108(70,)))))))) -13(-48(16,),44(-79,74))
- Author
- PRO1
- Language
- Catalan
- Official solutions
- Make
- User solutions
- Make