¿Cuál es la definición de la altura de un árbol?

Question

Me parece que no puede encontrar una respuesta definitiva para esto, yo estoy tratando de hacer algunas pruebas elementales sobre montones, pero esto es lo que me está arrojando un poco:

es un árbol vacío válida? Si es así, ¿cuál es su altura?
yo creo que esto sería 0.

¿Cuál es la altura de un árbol con un solo nodo?
Creo que esto sería 1, pero he visto definiciones donde es 0 (y si este es el caso, entonces no sé cómo explicar un árbol vacío).

Answer 1

Creo que debería echar un vistazo a Dictionary of Algorithms and Data Structures en el sitio web de NIST. No definition for height dice que un solo nodo es altura 0.

El definition of a valid tree incluye una estructura vacía. El sitio no menciona la altura de dicho árbol, pero según la definición de la altura, también debe ser 0.

Answer 2

La altura de un árbol es la longitud de la ruta desde la raíz de ese árbol hasta su nodo más lejano (es decir, el nodo de hoja más alejado de la raíz).

Un árbol con solo nodo raíz tiene altura 0 y un árbol con cero nodos se consideraría vacío. Un árbol vacío tiene una altura de -1. Por favor marque this.

Espero que esto ayude.

Answer 3

Lo he visto utilizado en ambos sentidos (contando un solo nodo como 0 o 1), pero la mayoría de las fuentes definiría un árbol de raíz como un árbol de altura 0, y no consideraría un 0-nodo árbol válido.

Answer 4

De acuerdo con Wikipedia, la altura de un (sub-) árbol con un solo nodo es 0. La altura de un árbol sin nodos sería -1. Pero creo que depende de ti, cómo defines la altura y tus pruebas deberían funcionar con cualquiera de las definiciones.

Answer 5

Si su árbol es una estructura de datos definida recursivamente que puede estar vacía o un nodo con un subárbol izquierdo y derecho (por ejemplo, árboles de búsqueda, o su montón), entonces la definición natural es asignar 0 al árbol vacío y 1 + la altura del subárbol más alto a un árbol no vacío.

Si su árbol es un gráfico, la definición natural es la ruta más larga desde la raíz hasta una hoja, por lo que un árbol con raíz única tiene profundidad 0. Normalmente, ni siquiera consideraría árboles vacíos en este caso.

Answer 6

La altura de un árbol es la longitud de la ruta más larga a un nodo terminal en cualquiera de sus elementos secundarios.

Wikipedia dice the height of an empty tree is -1. Estoy en desacuerdo. Un árbol vacío es literalmente solo un árbol que contiene un nodo terminal (un valor nulo o especial que representa un árbol vacío). Como el nodo no tiene hijos, la longitud de su ruta más larga debe ser empty sum = 0, no -1.

Del mismo modo, un árbol no vacío tiene dos hijos, por lo que por definición hay al menos una ruta> = 1 a un nodo de terminal.

Podríamos definir nuestro árbol de la siguiente manera:

type 'a tree = 
    | Node of 'a tree * 'a * 'a tree 
    | Nil 

let rec height = function 
    | Node(left, x, right) -> 1 + max (height left) (height right) 
    | Nil -> 0 

Answer 7

actully un defn perfectamente al crecimiento del árbol es el nivel D de la hoja de d camino más largo desde la raíz, más 1..accordin 2 fa este árbol defn s vacía , no tendrá ningún nivel. No puede considerar que tenía cero, porque el nivel de una raíz es cero. El nivel del árbol vacío es -1, entonces, el defnin 2 es -1 + 1 = 0..so ZERO sd altura de vacío árbol ... bt n muchos libros que han dado -1 bt no se han dado explicaciones