Subarbre. X98154

Feu la funció recursiva bool subArbre (arbreBin<int> A, arbreBin<int> B); tal que, donades dos arbres binaris d’enters positius, retorni true (false altrament) si el segon arbre és un subarbre del primer arbre.

Un arbre B és un subarbre d’un arbre A si existeix un node d’A a partir del qual puguem superposar-hi l’arbre B de manera que coincideixin tots els valors dels nodes de l’arbre B amb els valors de l’arbre A. Tingueu en compte que si bé tot l’arbre B ha d’aparèixer a A, a l’inrevés no cal que passi.

Per exemple, A2 és un subarbre d’A1 i d’A3, però A3 no és subarbre d’A1.

         A1            A2         A3

         1             1           1
        / \           / \         / \
       2   3         2   3       2   3
      / \ / \           /           / \
     5  6 7  8         7           7   2
                    

Entrada

La funció rep dos arbres binaris d’enters positius.

Sortida

true (false altrament) si el segon arbre és un subarbre de la primer arbre.

Observació

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

tar cvf program.tar subArbre.cpp

Observeu que per compilar us donem el Makefile,

la capçalera del mòdul funcional subArbre.hpp,

la implementació de l’arbre binar arbreBin.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.