java - recursivo - Confundido-Altura del árbol binario
imprimir arbol binario java (3)
El código 0 contará la raíz como altura 1 (la raíz debería ser 0). Lo que significa que todos los árboles subsiguientes serán demasiados
Estoy algo confundido entre la lógica de calcular la altura del árbol binario.
Código 1
public static int findHeight(Tree node) {
if(node == null)
return 0;
else {
return 1+Math.max(findHeight(node.left), findHeight(node.right));
}
}
Código 2
public static int findHeight(Tree node) {
if(node == null)
return -1;
else {
return 1+Math.max(findHeight(node.left), findHeight(node.right));
}
}
Creo que el segundo es correcto, ya que da la respuesta correcta para el siguiente código:
Tree t4 = new Tree(4);
Tree t2 = new Tree(2);
Tree t1 = new Tree(1);
Tree t3 = new Tree(3);
Tree t5 = new Tree(5);
t4.left = t2;
t4.right = t5;
t2.left = t1;
t2.right = t3;
// Prints "Height : 2" for Code 2
// Prints "Height : 3" for Code 1
System.out.println("Height : " + findHeight(t4));
Estoy confundido porque muchas otras respuestas de SO muestran la lógica para calcular la altura según el Código 1
Lógicas contradictorias
ACTUALIZAR:
Todos, tengo una duda básica sobre lo que es exactamente la altura del árbol?
1. ¿Es el no de nodos entre la raíz y el nodo más profundo del árbol (incluidos ambos - el nodo raíz y el más profundo)?
2. ¿Es el no de los bordes entre la raíz y el nodo más profundo del árbol?
O
3. ¿Es solo cuestión de implementar a cada individuo? ¿Ambos enfoques son correctos?
La diferencia radica en que un árbol vacío tiene una altura -1 o 0.
De acuerdo con Wikipedia :
La altura de un nodo es la longitud del camino descendente más largo hacia una hoja desde ese nodo. La altura de la raíz es la altura del árbol. La profundidad de un nodo es la longitud de la ruta a su raíz (es decir, su ruta raíz).
y
El nodo raíz tiene profundidad cero, los nodos hoja tienen altura cero, y un árbol con un solo nodo (por lo tanto, una raíz y una hoja) tiene profundidad y altura cero. Convencionalmente, un árbol vacío (árbol sin nodos, si está permitido) tiene profundidad y altura -1.
Así que puede que tengas razón, el segundo está de acuerdo con esto.
Por supuesto, estas son todas las definiciones: no me sorprendería mucho ver una definición que esté de acuerdo con la primera versión.
Su ejemplo es de altura 3 (t4 es una raíz, t4.left es t2, t2.left es t1) si su comprensión de la altura es (1 nodo raíz es de altura 1, nodo raíz con un niño o dos es de altura 2 , etc.)
t4.left = t2;
t4.right = t5;
t2.left = t1;
t2.right = t3;
Entonces el código 1 es correcto :))