ARBOLES GENERALIZADOS

TEMA 1. Árboles Generalizados
Son estructuras de datos no lineales, o también denominadas estructuras multienlazadas.
El árbol es una estructura de datos fundamental en informática, muy utilizada en todos sus campos, porque se adapta a la representación natural de informaciones homogéneas organizadas y de una gran comodidad y rapidez de manipulación. Esta estructura se encuentra en todos losdominios (campos) de la informática, desde la pura algorítmica (métodos de clasificación y búsqueda…) a la compilación (árboles sintácticos para representar las expresiones o producciones posibles de un lenguaje) o incluso los dominios de la inteligencia artificial (árboles de juegos, árboles de decisiones, de resolución, etc.)
Las estructuras tipo árbol se usan principalmente para representardatos con una relación jerárquica entre sus elementos, como son árboles genealógicos, tablas, etc.
Un árbol A es un conjunto finito de uno o más nodos, tales que:
1. Existe un nodo especial denominado RAIZ (v1) del árbol.
2. Los nodos restantes (v2, v3, …, vn) se dividen en m >= 0 conjuntos disjuntos denominado A1, A2, …, Am, cada uno de los cuales es, a su vez, un árbol. Estos árboles se llamansubárboles del RAIZ.
La definición de árbol implica una estructura recursiva. Esto es, la definición del árbol se refiere a otros árboles. Un árbol con ningún nodo es un árbol nulo; no tiene raíz.
La figura siguiente muestra un árbol en el que se ha rotulado cada nodo con una letra dentro de un círculo. Esta es una notación típica para dibujar árboles.

TERMINOLOGÍA Y REPRESENTACIÓN DE UN ÁRBOLGENERAL
La representación y terminología de los árboles se realiza con las típicas notaciones de las relaciones familiares en los árboles genealógicos: padre, hijo, hermano, ascendente, descendiente, etc. Sea el árbol de la figura:

Las definiciones a tener en cuenta son:
Raíz del árbol. Todos los árboles que no están vacíos tienen un único nodo raíz. Todos los demás elementos o nodos sederivan o descienden de él. El nodo raíz no tiene padre, es decir, no es el hijo de ningún elemento.
Nodo, son los vértices o elementos del árbol.
Nodo terminal u hoja (leaf node) es aquel nodo que no contiene ningún subárbol (los nodos terminales u hojas de la figura anterior son: E, F, K, L, H, I, J).
A cada nodo que no es hoja se asocia uno o varios subárboles llamados descendientes o hijos. Deigual forma, cada nodo tiene asociado un antecesor o ascendiente llamado padre.
Los nodos de un mismo padre se llaman hermanos.
Los nodos con uno o dos subárboles – no son hojas ni raíz – se llaman nodos interiores o internos.
Una colección de dos o más árboles se llama bosque (forest).
Todos los nodos tienen un solo padre – excepto el raíz – que no tiene padre.
Se denomina camino el enlaceentre dos nodos consecutivos y rama es un camino que termina en una hoja.
Cada nodo tiene asociado un número de nivel que se determina por la longitud del camino desde el raíz al nodo específico. Por ejemplo, en el árbol de la figura anterior:
Nivel 0 A
Nivel 1 B, C, D
Nivel 2 E, F, G, H, I, J
Nivel 3 K, L
La altura o profundidad de un árbol es el número máximo de nodos de una rama. Equivaleal nivel más alto de los nodos más uno.
El peso de un árbol es el número de nodos terminales.
Del árbol de la figura anterior, la altura es 4, y el peso es 7.
Fundamentos y terminología básica
Hasta ahora hemos visto estructuras de datos lineales, es decir, los datos estaban estructurados en forma de secuencia. Sin embargo, las relaciones entre los objetos no siempre son tan simples como paraser representadas mediante secuencias (incluso, en muchas ocasiones, es conveniente que no sea así), sino que la complejidad de las relaciones entre los elementos puede requerir otro tipo de estructura. En esas situaciones se pasaría a tener estructuras de datos no lineales. Este es el caso de la estructura de datos conocida como árbol.
   Los árboles establecen una estructura jerárquica entre...