tree - recursivo - Altura de un árbol con un solo nodo

clasificacion de arboles estructura de datos

Question

Según Wikipedia,

La altura de un árbol es la longitud de la ruta desde la raíz hasta el nodo más profundo del árbol. Un árbol (con raíz) con un solo nodo (la raíz) tiene una altura de cero (o uno).

No lo entiendo, ¿es cero o uno (o ambos)?

Answer 1

Depende de cómo quieras interpretar la altura de un árbol. en algunas aplicaciones, se interpreta que un árbol con un nodo tiene una altura de uno y otros consideran que tiene una altura de cero.

Answer 2

En mi opinión, la altura de un nodo raíz debería ser 0. Tiene sentido práctico ya que 2 ^ de altura también le proporciona la cantidad de nodos en ese nivel.

Answer 3

Es solo una suposición que haces para la descripción recursiva de la altura de un árbol binario. Puede considerar un árbol compuesto solo por un nodo con 0 altura o con 1 altura.

Si realmente quieres pensarlo de alguna manera, puedes pensar que

• es 0 si considera la altura como un recuento de bordes (de modo que un solo nodo no tenga ningún borde, por lo tanto, 0)
• es 1 si considera la altura como un recuento de nodos (de modo que un solo nodo cuenta como 1)

Esto es solo para describir la altura que tiene el árbol más pequeño y, en cualquier caso, cada vez que agregue un nodo descendente, también agregará un borde relacionado para que aumente.

En el ejemplo provisto en wikipedia:

Este árbol puede tener altura 4 (nodos) o 3 (bordes). Depende si lo estás contando por bordes o por nodos.

Answer 4

Suponiendo que está calculando la altura de manera recursiva en la clase de nodo, haría esto para devolver la altura sin incluir la altura de la raíz (código java):

int height(){
    int leftHeight = 0;
    int rightHeight = 0;
    if(left != null)
        leftHeight =+ left.height() + 1;
    if(right != null)
        rightHeight =+ right.height() + 1;
    return Math.max(leftHeight, rightHeight);
}

Si quieres incluir la altura de la raíz, entonces yo haría esto:

int height(){
    int leftHeight = 0;
    int rightHeight = 0;
    if(left != null)
        leftHeight =+ left.height();
    if(right != null)
        rightHeight =+ right.height();
    return Math.max(leftHeight, rightHeight) + 1;
}

Answer 5

Una de las ventajas de utilizar un recuento de nodos en lugar de un recuento de bordes es que distingue el caso vacío (nodos cero y nivel de nodo) del caso mínimo (un nodo y un nivel de nodo de uno). En algunos casos, un árbol vacío no será significativo, pero en otros casos un intento vacío será perfectamente legítimo.

Answer 6

Depende de la convención . No hay una respuesta "correcta" aquí. Me enseñaron que es 1. Pero el cero es igual de correcto.