2 - nov 2010

//Arbre d'altures

 

/* Considereu un arbre binari a de qualsevol tipus. Diem que l'arbre d'altures d'a és un altre arbre binari a_alt amb la mateixa forma que a, on cada element és l'altura del subarbre d'a que té com a arrel el corresponent de l'esmentat element.

 

Arbre<int> arbre_alt (Arbre<int> &a){

/*PRE: cert */

/*Post: el resultat és un arbre amb la mateixa forma que a, on cada element és l'altura del subarbre d'a que té com a arrel el corresponent de l'esmentat element */

 

        Arbre<int> b;

       

        if(not a.es_buit()){

                Arbre<int> a1,a2;

                int alt = altura(a);

                a.fills(a1,a2);

                Arbre<int> b1,b2;

                b1 = arbre_alt(a1);

                b2 = arbre_alt(a2);

                b.plantar(alt,b1,b2);

        }

return b;

}

 

int altura(Arbre<int>& a){

int alt;

if(a.es_buit()) alt = 0;

        else{

                Arbre<int> a1,a2;

                a.fills(a1,a2);

                int x = altura(a1);

                int y = altura(a2);

                if(x>y) alt = x;

                else alt = y;

        }

return alt;

}