Suma dels valors d'un arbre X23429
Implementeu una funció RECURSIVA 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(BinTree<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: main.cc, BinTree.hh, sumOfTree.hh. Us falta crear el fitxer sumOfTree.cc amb els corresponents includes i implementar-hi la funció anterior. Només cal que pugeu sumOfTree.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é 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.
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 46 47 28 14 20 2 14 37 4
Input
INLINEFORMAT 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
27 46 47 28 14 20 2 14 37 4
- Author
- PRO2
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++ Make