Saltar al contenido

Cálculo de la altura de un árbol binario

Verificamos exhaustivamente cada uno de los tutoriales de nuestra página web con la meta de enseñarte en todo momento información con la mayor veracidad y actualizada.

Solución:

Intentaré explicar cómo funciona este algoritmo recursivo:

height(10) = max(height(5), height(30)) + 1

height(30) = max(height(28), height(42)) + 1
height(42) = 0 (no children)
height(28) = 0 (no children)

height(5) =  max(height(4), height(8)) + 1
height(4) = 0 (no children)
height(8) = 0 (no children)

Así que si quieres calcular height(10)tiene que expandir la recursión hacia abajo y luego sustituir los resultados hacia atrás.

height(5)  = max(0, 0) + 1
height(30) = max(0, 0) + 1
height(10) = max(1, 1) + 1
height(10) = 2

EDITAR:

Como se señala en los comentarios:
height of binary tree = number of layers - 1

Por lo tanto, debe suponerse que la altura del nodo vacío es igual a -1, es decir:

height(empty) = -1 

o

height(null) = -1 

Por aquí

height(42) = max(height(null), height(null)) + 1
height(42) = max(-1, -1) + 1
height(42) = -1 + 1
height(42) = 0

He corregido el cálculo anterior.

La altura del árbol es la longitud del camino desde la raíz hasta el nodo más profundo del árbol. Aquí está el algoritmo más corto para hacerlo.

int height(Node root)
   if(root == null )
       return 0;
   return 1+maxheight(root.left), height(root.right);

¿Conoces la definición de altura del nodo? Lo respondería como la distancia más lejana a una hoja alcanzable (por lo que todas las hojas tienen una altura de 0) … ahora intente encontrar la altura de cada nodo de abajo hacia arriba … ese sería su algoritmo …

Aquí puedes ver las reseñas y valoraciones de los usuarios

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

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