Arbre de mides X56129


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.
BinTree<int> treeOfSizes(BinTree<int> t);

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

treeOfSizes(        3        ) =>         7
                    |                     |
             ------- -------       ------- -------
            |               |     |               |
            1               3     2               4
            |               |     |               |
             ----       ----       ----       ----
                 |     |               |     |
                 5     2               1     3
                       |                     |
                   ---- ----             ---- ----
                  |         |           |         |
                  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, BinaryTree.hh, treeOfSizes.hh. Us falta crear el fitxer treeOfSizes.cc amb els corresponents includes i implementar-hi la funció anterior. Només cal que pugeu treeOfSizes.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 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.

Public test cases

  • 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

              7
          |
      ---- ----
     |         |
     5         1
     |
 ---- ----
|         |
1         3
          |
      ---- ----
     |         |
     1         1

             7
             |
      ------- -------
     |               |
     3               3
     |               |
 ---- ----       ---- ----
|         |     |         |
1         1     1         1

               10
               |
           ---- ----
          |         |
          4         5
          |         |
      ----      ---- ----
     |         |         |
     3         1         3
     |                   |
 ---- ----           ----
|         |         |
1         1         2
                    |
                ----
               |
               1

             7
             |
      ------- -------
     |               |
     3               3
     |               |
 ---- ----       ---- ----
|         |     |         |
1         1     1         1

     3
     |
 ---- ----
|         |
1         1

4
|
 ----
     |
     3
     |
 ---- ----
|         |
1         1

1

          4
          |
      ----
     |
     3
     |
 ---- ----
|         |
1         1

        7
        |
         ----
             |
             6
             |
      ------- -------
     |               |
     3               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

    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
    PRO2
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++ Make