0

Me gustaría saber cómo hallar la profundidad de un árbol de un TAD Arbol dentro de la clase "Arbol".

Comprendo que un árbol puede ser recorrido en PreOrden, Orden Central y en PostOrden, pero supongo que habría que poner un nodo que vaya bajando hasta encontrarse con "null", entonces con un contador podríamos determinar la profundidad de dicho árbol.

Recorreríamos primero el subárbol izquierdo y luego el subárbol derecho, como en un PreOrden, y nos guardamos la profundidad mayor. Por ahora tendría esta idea, pero creo que debería ser mejor con un or ( || ):

      1
     / \
    3   2
public int profundidad(){

        int profundidad1 = 0;
        NodoArbol nodo = raiz;

        while(nodo != null){
            nodo = nodo.getDerecho();
            profundidad1++;
        }

        int profundidad2 = 0;
        NodoArbol nodo2 = raiz;

        while(nodo2 != null){
            nodo2 = nodo2.getIzquierdo();
            profundidad2++;
        }

        return Math.max(profundidad1, profundidad2);
    }

Luego, para probarlo, se haría desde la clase "Pruebas":

public class Pruebas {
    public static void main(String[] args) {

        Arbol arbol3 = new Arbol(3, null, null);

        Arbol arbol2 = new Arbol(2, null, null);

        Arbol arbol = new Arbol(1, arbol3, arbol2);

        System.out.println("Profundidad del árbol: " + arbol.profundidad());
    }
}

Tendríamos como salida de datos:

Preorden: 1  3  2  
Profundidad del árbol: 2
1
  • Por favor, edita la pregunta para limitarla a un problema específico con suficiente detalle para identificar una respuesta adecuada.
    – Comunidad Bot
    Commented el 6 jun. 2023 a las 9:48

1 respuesta 1

2

De la forma en que lo planteas en el código publicado en la pregunta, solo recorrerías los nodos derechos del nodo derecho de la raíz, y los nodos izquierdos del nodo izquierdo de la raíz.

Pero, dejarías de visitar todo el resto de nodos, digamos que tenemos el árbol:

        1               7
        2          3          14
        3        1   5      10   21
        4                  9
        5                 8

Ese código reportaría incorrectamente una profundidad de 3, cuando la profundidad real del árbol es 5.

Para dar la profundidad del arbol completo no hay de otra que visitar todos los nodos del árbol. Es decir, para cada nodo encontrado, habría que recorrer los nodos izquierdo y derecho. (el orden no es realmente importante, yo lo haría post order, solo por ser más simple).

Por lo mismo, como muchas operaciones en árboles, la solución más natural es la recursiva. Digamos, por ahora, que la clase NodoArbol tiene un método llamado getProfundidad() que simplemente mide la profundidad a partir de dicho nodo. Habría que implementar un método que mida la profundidad en la clase NodoArbol.

De esta manera, para el árbol completo, la solución sería simplemente llamar al método getProfundidad() del nodo raíz.

public int getProfundidad(){
    return raiz == null ? 0 : raiz.getProfundidad();
}

Ahora, la implementación en la clase NodoArbol podría ser algo así:

public int getProfundidad(){
    int pDerecha = nodoDerecho == null ? 0: nodoDerecho.getProfundidad();
    int pIzquierda = nodoIzquierdo == null ? 0 : nodoIzquierdo.getProfundidad();
    return 1 + Math.max(pDerecha, pIzquierda);
}

Cada nodo va añadiendo 1 a la maxima profundidad de sus nodos hijos, que es obtenida de manera recursiva. Si no tiene hijos, retornará 1.

Así, la profundidad se va calculando de abajo hacia arriba por el árbol, a partir de la visita a cada uno de sus nodos.

Estoy asumiendo los nombres de los miembros, la idea es que comprendas la idea que está detrás y puedas adaptar el código a tus propias clases.

8
  • Una pregunta, la solución que planteas, donde dices: "Así, la profundidad se va calculando de abajo hacia arriba por el árbol, a partir de la visita a cada uno de sus nodos." ¿No sería esto justamente una forma de recorrerlo distinta, es decir, en PostOrden? Commented el 6 jun. 2023 a las 9:35
  • 1
    Antonio, edité la pregunta. Digamos que efectivamente es post-order, que es el orden más natural para este caso, aunque como la visita es para efectos de cálculo y no se hace ninguna operación con los nodos, el orden realmente no es importante.
    – jachguate
    Commented el 6 jun. 2023 a las 9:39
  • Gracias, he estado mirando justamente tu implementación en la forma de "return ... ? 0 : ...", y me ha surgido la curiosidad al no comprenderlo, y he creado el post es.stackoverflow.com/questions/595894/variable-triestatal. Commented el 6 jun. 2023 a las 12:48
  • He intentado implementar tu código en la clase Arbol: java public int getProfundidadFinal(){ return raiz == null ? 0: raiz.getProfundidad(); } private int getProfundidad(){ NodoArbol nodoDerecho = raiz.getDerecho(); NodoArbol nodoIzquierdo = raiz.getIzquierdo(); int pDerecha = nodoDerecho == null ? 0: getProfundidad(); int pIzquierda = nodoIzquierdo == null ? 0: getProfundidad(); return 1 + Math.max(pDerecha, pIzquierda); } Commented el 6 jun. 2023 a las 17:20
  • 1
    @Antonio, sobre tu otra pregunta, la visité y creo que no tiene nada que ver con esta. Espero encuentres ayuda en eso también. Un saludo.
    – jachguate
    Commented el 6 jun. 2023 a las 17:25

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.