Camí en un arbre. X61097

Feu la funció recursiva

T camiEnArbre(BinaryTree<int>, int);

on el tipus T és:

typedef pair<bool,stack<int>> T;

tal que, donats un arbre binari $A$ d’enters sense repeticions i un enter $k$, retorni:

1. true (false altrament) si hi ha un camí de l’arrel a l’enter $k$ a l’arbre $A$.

2. Una pila amb el camí que va de l’arrel d’$A$ fins a $k$. L’arrel (inici del camí) serà el cim de la pila, i $k$ (el final del camí) serà el fons de la pila, i entre tots dos, hi haurà la resta del camí en ordre. Si $k$ no és a $A$, llavors aquesta pila tindrà un valor indefinit (no caldrà tenir-lo en compte).

La puntuació que podeu obtenir és la següent:

1. Solució correcta en els jocs de proves públics: 5 punts.

2. Solució correcta en els jocs de proves públics, especificació de la funció, H.I. i funció fita: 8 punts.

3. Solució correcta en els jocs de proves públics i privats: 7 punts.

4. Solució correcta en els jocs de proves públics i privats, especificació de la funció, H.I. i funció fita: 10 punts.

Una solució no recursiva implicarà un zero a tot l’exercici, independentment dels resultats que doni el jutge.

Entrada

La funció rep un arbre binari d’enters sense repeticions i un enter.

Sortida

Torna un booleà $b$ i una pila d’enters $p$. $b$ és true (false altrament) si l’enter és a l’arbre, i $p$ indica el camí de l’arrel (cim de $p$) fins a l’enter (fons de $p$).

Observació

Heu d’enviar la solució comprimida en un fitxer .tar:

tar cvf program.tar camiEnArbre.cpp

Observeu que per compilar us donem el Makefile, la capçalera del mòdul funcional camiEnArbre.hpp, la implementació de l’arbre binari BinaryTree.hpp, el fitxer utilitats.hpp i el programa principal program.cpp.

Jutge.org també us donarà un semàfor verd si envieu una solució iterativa, però no serà correcte ja que l’enunciat del problema demana que la solució enviada sigui recursiva.