Arboles

ESTRUCTURA DE DATOS
1. INTRODUCCION
En la práctica, la mayor parte de información útil no aparece aislada en forma de datos simples, sino que lo hace de forma organizada y estructurada. Los diccionarios, guías, enciclopedias, etc., son colecciones de datos que serían inútiles si no estuvieran organizadas de acuerdo con unas determinadas reglas. Además, tener estructurada la información suponeventajas adicionales, al facilitar el acceso y el manejo de los datos.
Por ello parece razonable desarrollar la idea de la agrupación de datos, que tengan un cierto tipo de estructura y organización interna.
Como tendremos ocasión de ver, la selección de una estructura de datos frente a otra, a la hora de programar es una decisión importante, ya que ello influye decisivamente en el algoritmoque vaya a usarse para resolver un determinado problema.

2. ÁRBOLES
2.1. Concepto
Un árbol es una estructura de datos, que puede definirse de forma recursiva como:
Una estructura vacía o
Un elemento o clave de información (nodo) más un número finito de estructuras tipo árbol, disjuntos, llamados subárboles. Si dicho número de estructuras es inferior o igual a 2, se tiene un árbol binario.Es, por tanto, una estructura no secuencial.
Otra definición nos da el árbol como un tipo de grafo: un árbol es un grafo acíclico, conexo y no dirigido. Es decir, es un grafo no dirigido en el que existe exactamente un camino entre todo par de nodos. Esta definición permite implementar un árbol y sus operaciones empleando las representaciones que se utilizan para los grafos. Sin embargo, en estasección no se tratará esta implementación.


2.2. Nomenclatura de Árboles
Raíz: es aquel elemento que no tiene antecesor; ejemplo: a.
Rama: arista entre dos nodos.
Antecesor: un nodo X 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.
Grado de un nodo: el número dedescendientes directos que tiene. Ejemplo: c tiene grado 2, d tiene grado 0, a tiene grado 2.
Hoja: nodo que no tiene descendientes: grado 0. Ejemplo: d
Nodo interno: aquel que tiene al menos un descendiente.
Nivel: número de ramas que hay que recorrer para llegar de la raíz a un nodo. Ejemplo: el nivel del nodo a es 1 (es un convenio), el nivel del nodo e es 3.
Altura: el nivel más alto delárbol.
Anchura: es el mayor valor del número de nodos que hay en un nivel. En la figura, la anchura es 3.
Aclaraciones: se ha denominado “a” a la raíz, pero se puede observar según la figura que cualquier nodo podría ser considerado raíz, basta con girar el árbol. Podría determinarse por ejemplo que “b” fuera la raíz, y “a” y “d” los sucesores inmediatos de la raíz “b”. Sin embargo, en lasimplementaciones sobre un computador que se realizan a continuación es necesaria una jerarquía, es decir, que haya una única raíz.
2.3. Algoritmos
Los Árboles tienes tres recorridos diferentes que son:
Pre-Orden
In-Orden
Post-Orden
2.4. Árboles Binarios
Hay un tipo especial de árbol muy usado en computación, denominado árbol binario, en el que de cada nodo pueden colgar, a lo más, dos subárboles.Estos se denominan subárbol derecho y subárbol izquierdo, y también son árboles binarios. La Figura 5.14 representa un árbol binario.

La forma usual de representar los árboles supone el uso de punteros, aunque también se puede hacer con vectores. En un árbol binario cada nodo está constituido por una parte de datos (INFORMACION) y dos punteros que indican la posición de sus hijos. Uno o ambosde los punteros pueden tener un valor nulo si del nodo no cuelgan subárboles. Cada nodo de un árbol será un registro que contiene al menos tres campos:
Un campo INFORMACION de datos de un cierto tipo.
Un puntero al nodo del subárbol izquierdo (que puede ser nulo).
Un puntero al nodo del subárbol derecho (que puede ser nulo).
La Figura 5.15 ilustra el uso de los punteros para construir el...