Calcular la altura de un árbol general en C++

El siguiente fragmento de código escrito en c++ calcula la altura de un árbol general de forma recursiva empleando plantillas de tipo T. Si bien esta pudiera no ser la forma más eficiente de realizar este procedimiento, es la que mejor escenifica el recorrido de la estructura de un árbol general. Tras el código he añadido un par de explicaciones, que se pueden completar con las dudas que dejes en los comentarios.

template <typename T>
template <typename T>
int Altura(const Agen<T> A, typename Agen<T>::nodo n){
    if( n == Agen<T>::NODO_NULO)
        return -1;
    else{
        // Tomamos al hijo de n
        typename Agen<T>::nodo hijo = A.hijoIzqdo(n);
        int max = -1;
        // Recorremos al mismo y a todos sus hermanos
        while(hijo != Agen<T>::NODO_NULO){
            int aux = Altura(A, hijo);
            if(aux > max)
                max = aux;
            hijo = A.hermDrcho(hijo);
        }
        return max + 1;
    }
}
}

A partir del nodo del árbol A, calculamos la altura, que se define como la longitud de la rama más larga que parte de n. Para aclararnos, la altura de un nodo hoja será 0 (-1 en el algoritmo) y la de la raíz será máxima. Si el nodo que encontramos es nulo, devuelve -1 para ajustar la solución, que de otra forma daría un entero de más. Si no, busca la máxima de las alturas entre el hijo izquierdo del nodo actual y su hermano derecho.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *