Diferència entre les sumes dels nivells d'un arbre binari X60436

Donat un arbre binari d’enters positius a, escriviu una funció recursiva que retorni la diferència entre la suma de tots els nodes d’a que es troben a nivell senar i la suma de tots els nodes d’a que es troben a nivell parell. El primer nivell d’un arbre no buit és 1.

Entrada

Com a entrada hi haurà la mida de l’arbre i els nodes de l’arbre binari en postordre. Per cada node s’indica el seu valor i el seu nombre de fills (2 fills, -1 indica un fill esquerre, 1 indica un fill dret o 0 fills).

Podeu utilitzar l’operador >> definit dins la classe arbreBin per llegir l’arbre binari.

Sortida

Com a sortida es mostrarà l’estructura de l’arbre binari d’entrada (podeu utilitzar l’operador << definit dins la classe arbreBin) i l’enter corresponent a la diferència entre la suma de tots els nodes de l’arbre d’entrada que es troben a nivell senar i la suma de tots els nodes de l’arbre d’entrada que es troben a nivell parell.

Observació

Es valorarà l’eficiència de la solució proposada. Es penalitzarà l’ús d’estructures de dades addicionals innecessàries.

Cal fer servir la classe arbreBin que us donem.

Heu d’enviar el fitxer amb la solució program.cpp comprimida en un fitxer .tar, que contindrà la funció demanada i el programa principal que la usi:

  tar cvf program.tar program.cpp

Observeu que per compilar us donem el Makefile i el mòdul arbreBin.