Fulles Parelles X88658

Implememteu una funció RECURSIVA que, donat un arbre binari, retorna el nombre de fulles a alçada parell de l’arbre.Aquesta es la capcelera:

 
Pre:
Post: Retorna el nombre de fulles de l'arbre t que estan a alçada parell.
int nfullparell(BinaryTree<int> t);

Aquí tenim un exemple de praràmetre d’entrada de la funció amb una representació visual (la representació visual no forma part del paràmetre d’entrada) i la corresponent sortida:

 
0(0(0(0(0,),0(0,0)),),)  => 3

---0
   ---0
      ---0
         ---0
         |  ---0
         |  ---0
         ---0
            ---0

Fixeuvos en que l’enunciat d’aquest exercici ja ofereix uns fitxers que haureu d’utilitzar pera compilar:Makefile, program.cpp, BinaryTree.hpp, nfullparell.hpp. Us falta crear el fitxer nfullparell.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 nfullparell.cpp

Entrada

Entrada

L’entrada té un nombre arbitrari de casos. Cada cas consisteix en una línia amb un string describint un arbre binari d’enters on tots els valors valen 0. 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

Sortida

Per cada cas, la sortida es un enter que correspon amb el nombre de fulles situades a alçada parell de l’arbre(l’arrel de l’arbre es troba a alçada 0).

Observació

Observació

La vostra funció i subfuncions que creeu han de treballar només amb arbres. Heu de trobar una solució RECURSIVA del problema. En les crides recursives, incloeu la hipòtesi d’inducció, és a dir una explicació del que es cumpleix després de la crida, i també la funció de fita/decreixement o una justificació de perquè la funció recursiva acaba.

Molt possiblement, una solució directa serà lenta, i necessitareu crear alguna funció recursiva auxiliar per a produïr una solució més eficient capaç de superar tots els jocs de proves.