Conceptos, Componentes y Propiedades de los Árboles

Conceptos

1. Altura de un nodo: en un árbol es el número de nodos del camino más largo de ese nodo a una hoja.
2. Altura del árbol: es la altura de la raíz, o 0 si el árbol es vacío.
3. Profundidad de un nodo: es la longitud del camino único que va desde la raíz hasta ese nodo.
4. Grado de un nodo: número de hijos de dicho nodo.
5. Grado de un árbol: es el mayor grado de los nodos que contiene.
6. Nivel de un nodo: se asigna en función al criterio siguiente:
1. Raíz: tiene nivel 1.
2. Nodo tiene nivel N: sus hijos tendrán nivel N+l.
3. El nº de niveles de un árbol es igual a la altura de su raíz, o a 0, si el árbol es vacío.

Conceptos menos utilizados son:

1. Longitud del camino externo: Suma de los niveles de cada nodo externo.
2. Longitud del camino interno: Suma de los niveles de cada nodo interno.

Componentes

1. RAÍZ: Todos los árboles que no están vacíos tienen un único nodo raíz. Todos los demás elementos o nodos derivan o descienden de él. El nodo Raíz no tiene Padre es decir no es hijo de ningún elemento.
2. PADRE: X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y.
3. HIJO: X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.
4. HERMANO: Dos nodos serán hermanos si son descendientes directos de un mismo nodo.
5. HOJA: Se le llama hoja o Terminal a aquellos nodos que no tienen ramificaciones (hijos).
6. NODO: Son los Vértices o elementos del Árbol.
7. NODO INTERIOR: Es un nodo que no es raíz ni Terminal.
8. GRADO: Es el número de descendientes directos de un determinado nodo.
9. GRADO DEL ÁRBOL: Es el máximo grado de todos los nodos del árbol.
10. 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

Propiedades

1. NODO indica un elemento, o ítem, de información.
2. Todo árbol que no es vacío, tiene un único nodo raíz.
3. Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. X es hijo de Y.
4. Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. X es padre de Y.
5. Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son hermanos.
6. Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja.
7. Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.
8. Grado es el número de descendientes directos de un determinado nodo.
9. Nivel es el número de arcos que deben ser recorridos para llegar a un determinado nodo.

Ejemplo:

1. 1. 8 es la raíz del árbol.
2. 2. es hijo de 8.
3. 10  es hijo de 8.
4.  1   es hijo de 3.
5. 14  es hijo de 10.
6. 13 es hijo de 14.
7. 3.-8    es padre de 3.
8. 3    es padre de 6.
9. 6    es padre de 7.
10. 10   es padre de 14.
11. 14   es padre de 13.
12. 4.- 3 y 10  son hermanos.
13. 1 y 6    son hermanos.
14. 4 y 7    son hermanos.
15. 5.- 1, 4, 7, 13  son nodos terminales u hojas.
16. 6.- 6, 14, 10,3  son nodos interiores.
17. El grado del nodo 8   es 2.
18. El grado del nodo 3   es 2.
19. El grado del nodo 6   es 2.
20. El grado del nodo 14 es 1.
21. El grado del nodo 1   es 0.
22. El grado del árbol es 3.El nivel del nodo 8   es 1
23. El nivel del nodo 3   es 2.
24. El nivel del nodo 6   es 3.
25. El nivel del nodo 10 es 2.
26. El nivel del nodo 13 es 4