¿Cómo calcular la altura de un árbol binario?
Analizar la relación entre la profundidad (altura) de un árbol binario y la profundidad de sus subárboles izquierdo y derecho. De la definición de profundidad del árbol binario se puede ver que la profundidad de un árbol binario debe ser el valor máximo de la profundidad de sus subárboles izquierdo y derecho más 1. Por lo tanto, primero es necesario encontrar la profundidad de los subárboles izquierdo y derecho respectivamente. La operación de "visitar el nodo" en el algoritmo es: encontrar el valor máximo de la profundidad de los subárboles izquierdo y derecho y luego sumar 1.
int Depth (BiTree T ){ // Devuelve la profundidad del árbol binario
if ( !T ) Depthval = 0;
else {
profundidadIzquierda = Profundidad( T->lchild );
profundidadDerecha= Profundidad( T->rchild );
valorprofundidad = 1 + (profundidadIzquierda > profundidadDerecha ?
profundidadIzquierda : profundidadDerecha);
}
devuelve valor de profundidad;
}
Información ampliada:
Un árbol binario con profundidad k y 2^k-1 nodos se denomina árbol binario completo. La característica de este tipo de árbol es que el número de nodos en cada nivel es el número máximo de nodos. En un árbol binario, excepto el último nivel, si todos los demás niveles están llenos y el último nivel está lleno o faltan varios nodos consecutivos a la derecha, entonces el árbol binario es un árbol binario completo. La profundidad de un árbol binario completo con n nodos es piso (log2n) +1. Un árbol binario completo con profundidad k tiene al menos 2k-1 nodos de hoja y como máximo 2k-1 nodos.
La profundidad de un árbol binario se acumula capa por capa comenzando desde el nodo raíz (su profundidad es 1) de arriba a abajo, mientras que la altura de un árbol binario se acumula capa por capa comenzando desde la hoja; nodo (su altura es 1) de abajo hacia arriba. Aunque la profundidad y la altura de un árbol son las mismas, la profundidad y la altura de un nodo específico del árbol son diferentes.
Enciclopedia Baidu: árbol binario