UNIDAD VI
Estructuras de datos
no lineales de tipo árbol

6.1  ÁRBOLES GENERALES

Las estructuras de datos no lineales resuelven los problemas que plantean las listas lineales y en los que cada elemento puede tener diferentes «siguientes» elementos, que introducen el concepto de estructuras de bifurcación. A estos tipos de datos se llaman Árboles.

Un árbol A es un conjunto finito de uno o más nodos, tales, que:

• Existe un nodo especial denominado RAIZ(v1) del árbol.
• 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 llaman subá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 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.

• Raíz: Todos los árboles que no están vacíos tienen un único nodo raíz. Todos los demás elementos o nodos se derivan o descienden de él. El nodo raíz no tiene padre,  es aquel elemento que no tiene antecesor; ejemplo: A.
• Nodo, son los vértices o elementos del árbol.
• Nodo terminal u Hoja: nodo que no contiene descendientes.
  Ejemplo:
  A cada nodo que no es hoja se asocia uno o varios subárboles llamados descendientes o hijos. De igual forma, cada nodo tiene asociado un antecesor o ascendiente llamado  padre.
  Los nodos de un mismo padre se llaman hermanos.
• Nodo interno: aquel que tiene al menos un descendiente.
• Una colección de dos o más subárboles se llama bosque.
• Todos los nodos tienen un solo padre –excepto la raíz – que no tiene padre.
• Camino, es el enlace entre dos nodos consecutivos.
• Rama: es un camino que termina en una hoja.
• Antecesor: un nodo X es es antecesor de un nodo Y si por alguna de las ramas de X se puede llegar a Y.
• Sucesor: un nodo X es sucesor de un nodo Y si por alguna de las ramas de Y se puede llegar a X.
• Nivel: número de ramas que hay que recorrer para llegar de la raíz a un nodo.
  Ejemplo:
  Nivel 0               A
  Nivel 1               B, C, D
  Nivel 2               E, F, G, H, I, J
  Nivel 3               K, L
• Altura: es el número máximo de nodos de una rama. Equivale al nivel más alto de los nodos más uno. Ejemplo, la altura de la figura es 4.
• Peso, es el número de nodos terminales. El peso del árbol de la figura es 7

6.1.2 Representación gráfica
Las representaciones gráficas de los árboles, pueden ser mostradas a continuación:

Las estructuras de datos no lineales resuelven los problemas que plantean las listas lineales y en los que cada elemento puede tener diferentes «siguientes» elementos, que introducen el concepto de estructuras de bifurcación. A estos tipos de datos se llaman Árboles.
Un árbol A es un conjunto finito de uno o más nodos, tales, que:

• Existe un nodo especial denominado RAIZ(v1) del árbol.
• 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 llaman subárboles del RAIZ.

6.2  ÁRBOLES BINARIOS

Introducción
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 los dominios (campos) de la informática, desde la pura algorítmica (métodos de clasificación y búsqueda…) ala 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 juego, árboles de decisiones, de resolución, etc.)

6.2.1 Terminología
Existe un tipo de árbol denominado árbol binario que puede ser implementado fácilmente en una computadora.

Un árbol binario es un conjunto finito de cero o más nodos (figura 3.3), tales que:

• Existe un nodo denominado raíz del árbol.
• Cada nodo puede tener 0, 1 o 2 subárboles, conocidos como subárbol izquierdo y subárbol derecho.

Dos árboles binarios se dice que son similares si tienen la misma estructura, y son equivalentes si son similares y contienen la misma información. (figura 3.4)
Un árbol binario está equilibrado si las alturas de los dos subárboles de cada nodo del árbol se diferencian en una unidad como máximo (figura 3.5).
Un árbol binario se llama completo si todos sus nodos tienen exactamente dos subárboles, excepto los nodos de los niveles más bajos de dos. Un árbol binario completo, tal que todos los niveles están llenos, se llama  árbol binario lleno. (figura 3.6)
Un árbol binario T de nivel h puede tener como máximo 2h-1 nodos.
La altura de un árbol binario lleno de n nodos es log2(n+1). Ala inversa, el número máximo de nodos de un árbol binario de altura h será 2h-1.
Se denomina árbol degenerado un árbol en el que todos sus nodos tienen solamente un subárbol, excepto el último.

Figura 3.3. Ejemplos de árboles binarios
a) expresión a+b/c;  
b)árbol con valores entreros

Figura 3.4. Árboles binarios
a) similares;   b)equivalente

Figura 3.5. Árboles binarios
a) equilibrados;   b)no equilibrados

Figura 3.6.  a)Árboles binarios lleno de altura 4
b)árbol binario completo de altura 3

Los árboles binarios pueden ser representados de dos modos diferentes:

• Mediante punteros (lenguajes Pascal y C)
• Mediante arrays o listas enlazadas
• Vinculando nodos, objetos con miembros que referencia otros objetos del mismo tipo.

En la representación por punteros cada nodo de un árbol será un registro que contiene al menos tres campos:

• Un campo de datos con un tipo de datos.
• Un puntero al nodo del subárbol izquierdo (que puede ser nulo-nil).
• Un puntero al nodo del subárbol derecho (que puede ser nulo-nil).

El lenguaje algorítmico se tendrá:

Tipo nodo_arbol
Punt= ^nodo_arbol
Nodo_arbol= registro
Elementos: <tipo elemento>
Subiz, subder: punt
Fin_registro

6.2.4 Recorrido de un árbol binario

Se denomina recorrido de un árbol el proceso que permite acceder una sóla vez a cada uno de los nodos del árbol.

Los algoritmos de recorrido de un árbol binario presentan tres tipos de actividades comunes:

• Visitar  el nodo raíz.
• Recorrer el subárbol izquierdo.
• Recorrer el subárbol derecho.

Estas tres secciones repartidas en diferentes órdenes proporcionan los diferentes recorridos del árbol. Los más frecuentes  tienen siempre en común recorrer primero el subárbol izquierdo y luego el subárbol derecho. Los algoritmos anteriores se llaman pre-orden, post-orden, in-orden y su nombre refleja el momento en que se visita el nodo raíz. En el in-orden el raíz está en el medio del recorrido, en el pre-orden el raiz está el primero y el post-orden el raíz está en el último.

Recorrido pre-orden

1. Visitar el raíz.
2. Recorrer el subárbol izquierdo en pre-orden
3. Recorrer el subárbol derecho en pre-orden.

Recorrido in-orden

1. Recorrer el subárbol izquierdo en  in-orden
2. Visitar el raíz.
3. Recorrer el subárbol derecho en in-orden.

Recorrido post-orden

1. Recorrer el subárbol izquierdo en  post-orden
2. Recorrer el subárbol derecho en post-orden.
3. Visitar el raíz.

6.2.5 Árbol binario de búsqueda

El árbol binario de búsqueda se construirá teniendo en cuenta las siguientes premisas:

• El primer elemento se utiliza para crear el nodo raíz.
• Los valores del subárbol deben ser tales que pueda existir un orden (entero, real, lógico o carácter e incluso definido por el usuario).

En cualquier nodo todos los valores del subárbol izquierdo del nodo son menor o igual al valor del nodo. De modo similar, todos los valores del subárbol derecha deben ser mayores que los valores del nodo .Un ejemplo de árbol binario de búsqueda:

En el ejemplo de la figura 3.8 las claves son números enteros. Dada la raíz 4, las claves del subárbol izquierdo son menores que 4, y las claves del subárbol derecho son mayores que 4. Esto se cumple también para todos los subárboles. Si se hace el recorrido de este árbol en orden central se obtiene una lista de los números ordenada de menor a mayor.

Una ventaja fundamental de los árboles de búsqueda es que son en general mucho más rápidos para localizar un elemento que una lista enlazada. Por tanto, son más rápidos para insertar y borrar elementos. Si el árbol está perfectamente equilibrado -esto es, la diferencia entre el número de nodos del subárbol izquierdo y el número de nodos del subárbol derecho es a lo sumo 1, para todos los nodos- entonces el número de comparaciones necesarias para localizar una clave es aproximadamente de log N en el peor caso. Además, el algoritmo de inserción en un árbol binario de búsqueda tiene la ventaja -sobre los arrays ordenados, donde se emplearía búsqueda dicotómica para localizar un elemento- de que no necesita hacer una reubicación de los elementos de la estructura para que esta siga ordenada después de la inserción. Dicho algoritmo funciona avanzando por el árbol escogiendo la rama izquierda o derecha en función de la clave que se inserta y la clave del nodo actual, hasta encontrar su ubicación; por ejemplo, insertar la clave 7 en el árbol de la figura 3.8 requiere avanzar por el árbol hasta llegar a la clave 8, e introducir la nueva clave en el subárbol izquierdo a 8.

El algoritmo de borrado en árboles es algo más complejo, pero más eficiente que el de borrado en un array ordenado.

Ahora bien, suponer que se tiene un árbol vacío, que admite claves de tipo entero. Suponer que se van a ir introduciendo las claves de forma ascendente.
Ejemplo: 1,2,3,4,5,6

Se crea un árbol cuya raíz tiene la clave 1. Se inserta la clave 2 en el subárbol derecho de 1.  A continuación se inserta la clave 3 en el subárbol derecho de 2.

Continuando las inserciones se ve que el árbol degenera en una lista secuencial, reduciendo drásticamente su eficacia para localizar un elemento. De todas formas es poco probable que se de un caso de este tipo en la práctica. Si las claves a introducir llegan de forma más o menos aleatoria entonces la implementación de operaciones sobre un árbol binario de búsqueda que vienen a continuación es en general suficiente.

Operaciones básicas sobre árboles binarios de búsqueda

- Búsqueda
Si el árbol no es de búsqueda, es necesario emplear uno de los recorridos anteriores sobre el árbol para localizarlo. El resultado es idéntico al de una búsqueda secuencial. Aprovechando las propiedades del árbol de búsqueda se puede acelerar la localización. Simplemente hay que descender a lo largo del árbol a izquierda o derecha dependiendo del elemento que se busca.
El algoritmo de búsqueda del elemento –clave x– se realiza comparándolo con la clave raíz del árbol. Si no es el mismo, se pasa al subárbol izquierdo o derecho, según el resultado de la comparación, y se repite la búsqueda en ese subárbol. La terminación del procedimiento se producirá cuando:

• Se encuentra la clave
• No se encuentra la clave; se continúa hasta encontrar un subárbol vacío.

- Inserción
Para insertar un elemento en el árbol A se ha de comprobar, en primer lugar, que el elemento no se encuentra en el árbol, ya que su caso no precisa ser insertado. Si el elemento no existe, la inserción se realiza en un nodo en el que al menos uno de los dos punteros IZQ o DER tenga valor nulo.
Para realizar la condición anterior se desciende en el árbol a partir del nodo raíz, dirigiéndose de izquierda a derecha de un nodo, según que el valor a insertar sea inferior o superior al valor del campo clave INFO de este nodo. Cuando se alcanza un nodo del árbol en que no se puede continuar, el nuevo elemento se engancha a la izquierda o derecha de este nudo en función de que su valor sea inferior o superior al del nodo alcanzado.

- Borrado
La eliminación de un elemento debe conservar el orden de los elementos del árbol. Se consideran diferentes casos, según la posición del elemento o nodo en el árbol:

• Si el elemento es un hoja, se suprime simplemente.
• Si el elemento no tiene más que un descendiente, se sustituye entonces por eso descendiente.
• Si el elemento tiene dos descendientes, se sustituye por el elemento inmediato inferior situado lo más a la derecha posible de su subárbol izquierdo.

Para poder realizar estas acciones será preciso conocer la siguiente información del nodo a eliminar:

• Conocer su posición en el árbol
• Conocer la dirección de su padre
• Conocer si el nodo a eliminar tiene hijos, si son 1 o 2 hijos, y en el caso de que sólo sea uno, si es hijo derecho o izquierdo.

6.2.6 Transformación de un árbol general a árbol binario

Dados que los árboles binarios es la estructura fundamental en la teoría de árboles, será preciso disponer de algún mecanismo que permita la conversión de un árbol general en un árbol binario.
El algoritmo de conversión tiene tres pasos:

1. La raíz de B es la raíz de A.
2.  

• Enlazar al nodo raíz con el camino que conecta el nodo más a la izquierda (su hijo)
• Enlazar este nodo con los restantes descendientes del nodo raíz en un camino, con lo que se forma el nivel 1.
• A continuación, repetir los pasos a) y b) con los nodos del nivel 2, enlazando siempre en un mismo camino todos los hermanos –descendientes del mismo nodo- . Repetir estos pasos hasta llegar al nivel más alto.

     3. Girar el diagrama resultante 45º para diferenciar entre los subárboles izquierdo y          derecho.

Siguiendo los pasos del algoritmo:

Paso 3:
Obsérvese que no existe camino entre E y F, debido a que no son descendientes del árbol original, ya que ellos tienen diferentes padres B y C. En el árbol binario resultante los punteros izquierdos son siempre de un nodo padre a su primer hijo (más a la izquierda) en el árbol general original. Los punteros derechos son siempre desde un nodo de sus descendientes en el árbol original.

HERRAMIENTAS, MATERIALES Y EQUIPOS:

• Hojas blancas, lápiz
• Lenguaje C#
• Pc

PROCEDIMIENTO:

• Resuelva cada uno de los ejercicios que se indican.
• Elabore el algoritmo en los problemas  que se requieran.
• Codifique los algoritmos en Lenguaje C#.
• Compruebe que la ejecución y sus resultados  sean correctos.

EVIDENCIAS
            Documentos:

• Hoja de presentación
• Algoritmos de cada uno de los ejercicios.
• Diagramas de Flujo de cada método.
• Impresión del Código en el lenguaje C#.
• Impresión de la ejecución. (Pantalla con resultados)
• Conclusión.

           Programas:

• Toda la carpeta
• Todos los ejercicios serán entregados en un solo disco. (El disco debe traer su etiqueta correspondiente).

PLANTEAMIENTO DE PROBLEMAS:

7.1 Crear un archivo de datos en el que cada línea contenga la siguiente información:

Columnas        1-20     Nombre
                     21-31    Número de la Seguridad Social
                     32-78    Dirección

Escribir un programa  que lea cada registro de datos de un árbol, de modo que cuando el árbol se recorra utilizando recorrido en orden, los números de la seguridad social se orden en orden ascendente. Imprimir una cabecera <<DATOS DE EMPLEADOS ORDENADOS POR NÚMERO SEGURIDAD SOCIAL>>. A continuación se han de imprimir los tres datos utilizando el siguiente formato de salida:
Columnas        1-11     Número de la Seguridad Social
                    25-44     Nombre
                    58-104 Dirección

7.2.  Se dispone de un árbol binario de elementos de tipo integer. Escribir funciones que calculen:

• La suma de sus elementos.
• La suma de sus elementos que son múltiplos de 3.

7.3.  Construir un procedimiento recursivo para encontrar una determinada clave en un árbol binario de búsqueda.

7.4. Dado un árbol binario de búsqueda construir su árbol espejo. (Árbol espejo es el que se construye a partir de uno dado, convirtiendo el subárbol izquierdo en subárbol derecho y viceversa).

7.5. En tres árboles binario de búsqueda (ORO, PLATA, COBRE) están representados los medallistas de cada una de las pruebas de una reunión atlética. Cada nodo tiene la información: nombre de la prueba, nombre del participante y nacionalidad. El árbol ORO almacena los atletas ganadores de dicha medalla, y así respectivamente con los árboles PLATA y COBRE. El criterio de ordenación de los árboles ha sido el nombre del atleta. Escribir los procedimientos/funciones necesarias para resolver este supuesto:
Dado el nombre de un atleta y su nacionalidad, del cual no se sabe si tiene medalla, encontrar un equipo de atletas de su mismo país, incluyendo al mismo que tenga una suma de puntos comprendida entre N y M. Hay que tener en cuenta que una medalla de oro son 10 puntos, plata 5 puntos y cobre 2 puntos.

Conclusión

La estructura árbol más utilizada normalmente es el árbol binario. Un árbol binario es un árbol en el que cada nodo tiene como máximo dos hijos, llamados subárbol izquierdo y subárbol derecho.

En un árbol binario cada elemento tiene cero, uno o dos hijos. El nodo raíz no tiene un padre pero sí cada elemento restante. Cuando un elemento y tiene un padre x, x es un antecesor o antecedente del elemento y.

Los árboles binarios presentan dos tipos característicos: árboles binarios de búsqueda y árboles binarios de expresiones. Los árboles binarios de de búsqueda se utilizan fundamentalmente para mantener una colección ordenada de datos y los árboles binarios de expresiones para almacenar expresiones.