Arboles (estructura de datos)

Árboles

Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en computación. Dinámicas, puesto que la estructura de un árbol puede cambiar durante la ejecución del programa. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos.

Árboles en general.

Un árbol es una estructura jerárquica aplicada sobre unacolección de elementos llamados nodos; uno de los cuales es conocido como raíz, y un conjunto finito de líneas dirigidas, denominadas ramas. Además se crea una relación o parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, etcétera.
Formalmente se define un árbol de tipo T como una estructura homogénea que es la concatenación de un elemento detipo T junto con un número finito de árboles disjuntos, llamados subárboles.
Se utiliza la recursión para definir un árbol porque representa la forma más apropiada y por que es una característica inherente de los mismos.

Gráficamente una estructura árbol puede representarse de diferentes formas y todas ellas equivalentes.
[pic]
Fig. 5.1 Diferentes formas de representar un árbol.Características y propiedades de los árboles

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 Xes 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 terminalu 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.
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 deniveles de todos los nodos del árbol.

Ejemplo. Dado el árbol general de la figura, se hacen sobre el las siguientes consideraciones.
[pic]
Fig. 5.2 Árbol general

|A es la raíz del árbol. |B y C son hermanos. |
| |D, E y Fson hermanos. |
|B es hijo de A. |G y H son hermanos. |
|C es hijo de A. |J y K son hermanos. |
|D es hijo de B.| |
|E es hijo de N. |5. I, E, J, K, G y L son nodos terminales |
|L es hijo de H. |u hojas. |
|| |
|A es padre de B |6. B, D, F, C y H son nodos interiores. |
|B es padre de D. | |
|D es padre de I....