Hay tres propiedades importantes de los árboles: altura, profundidad y nivel, junto con el borde y el camino y el árbol (estructura de datos) en wiki también los explica brevemente:
Borde
Borde: conexión entre un nodo a otro.
- Dado un gráfico de N vértices con m1 bordes unidireccionales y m2 bordes bidireccionales, ¿cómo podemos dirigir los bordes bidireccionales de modo que no tengamos ninguna caminata cerrada?
- ¿Cuál es el mejor factor de contracción para un tipo de peine? ¿Por qué?
- ¿Cómo debo definir el orden de mi cromosoma en mi algoritmo genético?
- ¿Cómo funciona la detección de vandalismo de Wikipedia?
- ¿Cómo puedes visualizar algoritmos?
Un ejemplo de borde se muestra arriba entre A y B. Básicamente, un borde es una línea entre dos nodos, o un nodo y una hoja .
Camino
Ruta: una secuencia de nodos y bordes que conectan un nodo con un descendiente.
Una ruta comienza desde un nodo y termina en otro nodo o una hoja. Por favor, no mire los siguientes puntos:
- Cuando hablamos de una ruta, incluye todos los nodos y todos los bordes a lo largo de la ruta, no solo los bordes .
- La dirección de una ruta es estrictamente de arriba a abajo y no se puede cambiar en el medio. En el diagrama, no podemos hablar realmente de una ruta de B a F, aunque B está por encima de F. Además, no habrá una ruta que comience desde una hoja o desde un nodo secundario hacia un nodo primario. ( [1] )
Altura
Altura del nodo: la altura de un nodo es el número de bordes en el camino descendente más largo entre ese nodo y una hoja.
Al principio, podemos ver que la definición wiki anterior tiene un término redundante, hacia abajo , dentro. Como ya sabemos en la sección anterior, la ruta solo puede ser hacia abajo.
Al mirar a la altura:
- Cada nodo tiene altura. Entonces B puede tener altura, también A , C y D.
- La hoja no puede tener altura ya que no habrá camino a partir de una hoja.
- Es el camino más largo desde el nodo a una hoja . Entonces, la altura de A es el número de bordes de la ruta hacia E , NO hacia G. Y su altura es de 3.
La altura de la raíz es 1.
Altura del árbol: la altura de un árbol es el número de bordes en el camino descendente más largo entre la raíz y una hoja.
Entonces la altura de un árbol es la altura de su raíz .
Con frecuencia, se nos puede hacer la pregunta: ¿cuál es el número máximo de nodos que puede tener un árbol si la altura del árbol es h? . Por supuesto, la respuesta es 2h − 1 [matemáticas] 2h − 1 [/ matemáticas]. Cuando h = 1 [matemática] h = 1 [/ matemática], el número de nodo dentro es 1, que es solo la raíz; también cuando un árbol solo tiene raíz, la altura de la raíz es 1. Por lo tanto, las dos inducciones coinciden.
¿Qué tal dar una altura de 0? Entonces significa que no tenemos ningún nodo en el árbol; pero aun así podemos tener hojas adentro. Por eso, en la mayoría de los idiomas, el tipo de árbol puede ser solo una hoja.
escriba 'a bst = El | Hoja El | Nodo de 'a bst *' a * 'a bst
Además, cuando usamos 2h − 1 [matemática] 2h − 1 [/ matemática] para calcular el número máximo de nodos, las hojas no se tienen en cuenta. La hoja no es nodo . No lleva clave ni datos, y actúa solo como una señal de STOP. Necesitamos recordar esto cuando tratamos con las propiedades de los árboles.
Profundidad
Profundidad: la profundidad de un nodo es el número de aristas desde el nodo hasta el nodo raíz del árbol.
Ya no nos importa la ruta cuando aparece la profundidad. Solo contamos cuántos bordes entre el nodo de orientación y la raíz, ignorando las direcciones. Por ejemplo, la profundidad de D es 2.
Recuerde que cuando hablamos de altura, en realidad implicamos una línea de base ubicada en la parte inferior. Para depath, la línea base está en la parte superior, que es el nivel raíz. Por eso lo llamamos profundidad.
Tenga en cuenta que la profundidad de la raíz es 0 .
Nivel
Nivel: el nivel de un nodo se define por 1 + el número de conexiones entre el nodo y la raíz.
Simplemente poniendo , el nivel es la profundidad más 1.
Lo importante a recordar es que cuando se habla de nivel, comienza desde 1 y el nivel de la raíz es 1 . Debemos tener cuidado con esto al resolver problemas relacionados con el nivel.
