Pes Màxim en un Arbre. X86754

Les fulles d’un arbre binari són els nodes que no tenen ni fill dret ni fill esquerre. Un camí és una seqüència de nodes d’un arbre A [a₁, a₂, …, a_i, a_i+1, …, a_n] tal que a₁ és l’arrel d’A, a_n és una fulla, i per a tot a_i (i < n) tenim que a_i+1 és el fill de a_i. Un arbre A té tants camins com fulles.

El pes d’un camí [a₁, a₂, …, a_i, a_i+1, …, a_n] és:

Feu la funció recursiva

int pesMaxim (arbreBin<int> A);

tal que, donat un arbre binari de distàncies A, torni el màxim dels pesos de tots els camins que hi ha a l’arbre A.

             A1            A2         A3
    
             4             2           9
            / \           / \         / \
           2   5         12  3       2   3
          / \ / \           /           / \
         5  6 3  1         7           7   2
                    

Per exemple, per a l’arbre A1 la funció tornaria 12, que és el pes del camí [4,2,6] o la del camí [4,5,3]. Per a l’arbre A2 la funció tornaria 14, que és el pes del camí [2,12]. Per a l’arbre A3 la funció tornaria 19, que és el pes del camí [9,3,7].

El pes màxim d’un arbre buit és 0.

Entrada

La funció rep un arbres binari d’enters, on tots els enters són més grans o iguals a 0.

Sortida

El màxim dels pesos de tots els camins que hi ha a l’arbre. El pes màxim d’un arbre buit és 0.

Observació

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

tar cvf program.tar pesMaxim.cpp

Observeu que per compilar us donem el Makefile,

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

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