3

Tengo una clase tree para representar arboles orientados (No binarios). Los nodos son representados por una celda, que tiene el metodo lchild() que nos da el hijo mas izquierdo y right() o siplemente incrementando (como en list) para obtener su hermano que le sigue. Acá dejo codigo para listar orden previo, para tener en cuenta.

void oprev(tree<int> &T, tree<int>::iterator p){
tree<int>::iterator q;
if (p == T.end()){ 
    return;
}
cout<<*p<<" ";
q = p.lchild();
while( q != T.end() ){
    oprev (T, q++);
}

void oprev(tree<int> &T){
oprev(T,T.begin());}

Necesito calucar la altura de un arbol. Tengo este codigo pero no es correcto

int altura(tree<int> &T,tree<int>::iterator p, int &x){
tree<int>::iterator q;
if (p == T.end()){ 
    return x;
}
q = p.lchild();
while( q != T.end() ){
    altura(T, q++,x);
}
if(p.lchild()!=T.end()){
    x++;
}
return x;}

Teniendo este arbol.

AOO

Como altura obtengo 5.

Reconozco que el error está en que el contador, a veces suma de vuelta cuando pasa por niveles que anteriormente ya ha pasado. No se como puedo evitar esto. Desde ya gracias. Saludos

2 respuestas 2

4

Si por "altura del árbol" te refieres a cuán largas son sus "ramas" no lo estás haciendo bien. Tienes varios problemas de concepto.

Propuesta.

Añade a tu clase plantilla tree una función altura que consultará a todos los nodos de su raíz cuán profundos son y se quedará con el máximo de ellos:

int tree::altura()
{
    int a = 0;

    for (auto &nodo : raiz)
        a = std::max(a, deep(nodo, 0))

    return a;
}

El código anterior asume que tu clase tree tiene un nodo llamado raiz y que dicho nodo provee las funciones begin y end.

La función anterior llama a la función recursiva deep que hace casi lo mismo que la función altura con la diferencia que a cada nivel de recursión incrementa el nivel en 1, para ello esta función debe recibir el nodo desde el que calcular y la profundidad desde la que empezar a contar:

int tree::deep(Nodo &n, int nivel)
{
    int a = nivel;

    for (auto &nodo : raiz_del_arbol)
        a = std::max(a, deep(nodo, nivel + 1))

    return a;
}

Si el nodo al que hemos llegado no tiene hijos, su nivel será el nivel proveído en la llamada.

Otras cosas a tener en cuenta.

Tienes unos fallos de diseño que me gustaría comentarte:

  • No uses funciones libres para hacer estas operaciones, estas funciones te obligan a exponer los datos de tu clase rompiendo así la encapsulación.
  • Si realmente debes usar funciones libres, usa una función plantilla, o te verás obligado a crear una versión por cada instanciación de la plantilla tree.
2

Estás contando el número de hijos, no la altura.

La diferencia es que, para un nodo cualquiera, la altura será el máximo de las alturas de los dos hijos, no la suma de las alturas.

Así que tira hacia (pseudocódigo para no quitarte el placer de programar):

int altura(nodo n) {

   int alturaDerecha = 0; int alturaIzquierda = 0;

   si es n un nodo terminal {
      return 1;
   }

   si existeHijoDerecho de n {
      alturaDerecha = altura(n.hijoDerecho());
   }

   si existeHijoIzquierdo de n {
      alturaIzquierda = altura(n.hijoIzquierdo());
   }

   int alturaHijos = max(alturaDerecha, alturaIzquierda);
   return alturaHijos + 1;
}

Si lo encuentras más legible, puedes mover la comprobación del nodo terminal antes de buscar las alturas de los hijos.

2
  • El problema es que no es un arbol binario, en un mismo nivel puedo tener muchos nodos. Edite el posta para dejarlo mas claro. No se si me explico Commented el 11 oct. 2017 a las 14:49
  • 1
    El algoritmo seguiría siendo el mismo, básicamente. Sólo tienes que quedarte con la altura máxima de los N hijos que tenga el nodo actual. Commented el 11 oct. 2017 a las 14:54

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.