Suma dels valors d'un arbre (iteratiu) X84228

Statement

html

Implementeu una funció ITERATIVA que, donat un arbre binari d’enters, retorna la suma dels seus valors. Aquesta és la capcelera:

// Pre:
// Post: Retorna la suma dels valors de t
int sumOfTree(BinaryTree<int> t);

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

t:           3
             |
      ------- -------
     |               |
     1               4
     |               |
 ---- ----       ----
|         |     |
2         5     1

=>

16

Fixeu-vos que l’enunciat d’aquest exercici ja ofereix uns fitxers que haureu d’utilitzar per a compilar: Makefile, program.cpp, BinaryTree.hpp, sumOfTree.hpp. Us falta crear el fitxer sumOfTree.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 sumOfTree.cpp

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é la corresponent suma de l’arbre. Fixeu-vos en que el programa que us oferim ja s’encarrega d’escriure aquesta suma. Només cal que implementeu la funció abans esmentada.

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

Input

INLINEFORMAT
0(55(29,-47(-15,98)),-18)
-94(82(-21,80),-16(63,-85))
-27(-50(6(13,-56),),23(2,36(-2(-37,),)))
-56(-5(-100,-37),7(-70,-18))
5(-3,-32)
50(,-23(-17,91))
41
91(59(75,-46),)
55(,62(-31(-10,69),-74(67,)))
-56
12(96(-22(88,),31(15,-92)),-47(70,))
-58(4,-1(27,-35))
78
-91(89(35(-95,-24),-50(,77)),-95)
-69
89(-93(,-72),-31(-76,-91))
-25(93,76)
32(-71,73(-68(,-12(,-70)),-86(-61(-68,58),-39)))
68(-10(22,60),91)
89(-7(-20,37),)

Output

Information

Author: PRO1
Language: Catalan
Official solutions: Make
User solutions: Make