java - programar - Altura de un árbol binario
clasificacion de arboles estructura de datos (4)
Es una función recursiva. Se dice que la altura de un árbol es 1 + la altura de su rama más alta.
¿BFS es una búsqueda de amplitud? No estoy seguro de la diferencia en eficiencia, pero me gusta la simplicidad de la función recursiva.
Considera el siguiente código:
public int heightOfBinaryTree(Node node)
{
if (node == null)
{
return 0;
}
else
{
return 1 +
Math.max(heightOfBinaryTree(node.left),
heightOfBinaryTree(node.right));
}
}
Quiero saber el razonamiento lógico detrás de este código. ¿Cómo se le ocurrió a la gente? ¿Algunos tienen una prueba inductiva?
Además, pensé simplemente hacer un BFS con la raíz del árbol binario como el argumento para obtener la altura del árbol binario. ¿Es el enfoque anterior mejor que el mío? ¿Por qué?
La altura de un árbol es la longitud del camino descendente más largo desde su raíz. Esta función es una forma recursiva de contar los niveles de un árbol binario. Simplemente incrementa los contadores a medida que desciende del árbol, devolviendo el contador máximo (el contador en el nodo más bajo).
Espero haber ayudado.
La lógica detrás de ese código es:
dado que un nodo tendrá dos hijos, la altura del Árbol será máxima de las alturas del árbol cuyas raíces sean el niño izquierdo y el niño derecho, y por supuesto +1 para la caminata hacia los niños.
Como puede ver, la descripción anterior es recursiva y también lo es el código.
BFS también debería hacerlo, pero sería una exageración tanto en la implementación como en la complejidad del espacio / tiempo.
Hay un dicho, funciones recursivas aunque difíciles de entender, pero son muy elegantes de implementar.
if (node == null)
{
return 0;
}
Los hijos de los nodos de hoja son null . Por lo tanto, esto está diciendo que una vez que hemos pasado las hojas, no hay más nodos.
Si no pasamos los nodos hoja, tenemos que calcular la altura y este código lo hace recursivamente.
return 1 +
El nodo actual agrega una altura de 1 a la altura del subárbol que se está calculando actualmente.
Math.max(heightOfBinaryTree(node.left),
heightOfBinaryTree(node.right));
Calculamos recursivamente la altura del subárbol izquierdo ( node.left ) y el subárbol derecho ( node.right ). Dado que estamos calculando la profundidad máxima, tomamos el máximo de estas dos profundidades.
He mostrado anteriormente que la función recursiva es correcta. Entonces, al llamar a la función en el nodo padre, se calculará la profundidad de todo el árbol.
Aquí hay una representación gráfica de la altura de un árbol de este documento . h es la altura del árbol, hl y hr son las alturas de los subárboles izquierdo y derecho, respectivamente.
Además, pensé simplemente hacer un BFS con la raíz del árbol binario como el argumento para obtener la altura del árbol binario. ¿Es el enfoque anterior mejor que el mío? ¿Por qué?
El código que proporcionó es una forma de DFS. Como debe procesar todos los nodos para encontrar la altura del árbol, no habrá diferencia de tiempo de ejecución entre DFS y BFS, aunque BFS utilizará memoria O (N) mientras que DFS utilizará la memoria O (logN). BFS también es un poco más complejo de codificar, ya que requiere una cola mientras que DFS hace uso de la pila recursiva "incorporada".