Arbre d'alçades X13384
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. BinTree<int> treeOfHeights(BinTree<int> t);
Aquí tenim un exemple de paràmetre d’entrada de la funció i la corresponent sortida:
treeOfHeights( 3 ) => 4
| |
------- ------- ------- -------
| | | |
1 3 2 3
| | | |
---- ---- ---- ----
| | | |
5 2 1 2
| |
---- ---- ---- ----
| | | |
1 7 1 1
Fixeu-vos que l’enunciat d’aquest exercici ja ofereix uns fitxers que haureu d’utilitzar per a compilar: main.cc, BinTree.hh, treeOfHeights.hh. Us falta crear el fitxer treeOfHeights.cc amb els corresponents includes i implementar-hi la funció anterior. Només cal que pugeu treeOfHeights.cc al jutge.
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 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.
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
4
|
---- ----
| |
3 1
|
---- ----
| |
1 2
|
---- ----
| |
1 1
3
|
------- -------
| |
2 2
| |
---- ---- ---- ----
| | | |
1 1 1 1
5
|
---- ----
| |
3 4
| |
---- ---- ----
| | |
2 1 3
| |
---- ---- ----
| | |
1 1 2
|
----
|
1
3
|
------- -------
| |
2 2
| |
---- ---- ---- ----
| | | |
1 1 1 1
2
|
---- ----
| |
1 1
3
|
----
|
2
|
---- ----
| |
1 1
1
3
|
----
|
2
|
---- ----
| |
1 1
4
|
----
|
3
|
------- -------
| |
2 2
| |
---- ---- ----
| | |
1 1 1
1
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
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))
- Author
- PRO2
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++ Make