Las siguientes son las características y propiedades más importantes de los árboles en general:
a) Todo árbol que no es vacío, tiene un único nodo raíz.
b) Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. en este caso es común utilizar la expresión X es hijo de Y.
c) Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. en este caso es común utilizar la expresión X es padre de Y.
d) Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son hermanos.
e) Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja.
f) Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.
g) Grado es el número de descendientes directos de un determinado nodo. Grado del árbol es el máximo grado de todos los nodos del árbol, es decir, el grado más alto entre todos los nodos.
h) Nivel es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.
i) Altura del árbol es el máximo número de niveles de todos los nodos del árbol.
A continuación se presenta un ejemplo para clarificar estos conceptos.
1. A es la raíz del árbol.
2. B es hijo de A.
C es hijo de A.
D es hijo de B.
E es hijo de B.
L es hijo de H.
3. A es padre de B.
B es padre de D.
D es padre de I.
C es padre de G.
H es padre de L.
4. B y C son hermanos.
D, E y F son hermanos.
G y H son hermanos.
J y K son hermanos.
5. I, E, J, K, G y L son nodos terminales u hojas.
6. B, D, F, C y H son nodos interiores.
7. El grado del nodo A es 2.
El grado del nodo B es 3.
El grado del nodo C es 2.
El grado del nodo D es 1.
El grado del nodo E es 0.
El grado del árbol es 3.
8. El nivel del nodo A es 1.
El nivel del nodo B es 2.
El nivel del nodo D es 3.
El nivel del nodo C es 2.
El nivel del nodo L es 4.
9. La altura del árbol es 4.
No hay comentarios.:
Publicar un comentario