Estructuras Dinamicas De Informacion

ESTRUCTURAS DINÁMICAS DE INFORMACIÓN: ARBOLES

1) Arboles

En ciencias de la computación, un árbol es una estructura de datos ampliamente usada que emula la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o mas nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b, si existe un enlacedesde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja.
El árbol También se define como una estructura de datos no lineal. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos ytablas de contenidos. Entre otros tenemos un tipo especial de de árbol que es, llamado árbol binario, que puede ser implementado fácilmente en la computadora.

2) Arboles Generales

3) Arboles Binarios

La única manera de construir un árbol binario con un nodo consiste en hacer que el nodo sea su raíz y que estén vacíos sus subárboles izquierdo y derecho (representan un apuntador aNULL), esto significa que se trata de un árbol ordinario. Con dos nodos en el árbol, uno de ellos será la raíz y el otro estará en un subárbol. Así, uno de los subárboles de la izquierda o derecha debe estar vacío y el otro contendrá un nodo. De ahí que haya dos árboles binarios diferentes con dos nodos.

En el caso de un árbol binario con tres nodos, uno de estos será la raíz y los otros dos sedividirán entre los subárboles de la izquierda y derecha en una de las siguientes formas: 2 + 0, 1 + 1 y 0 + 2.Como hay dos árboles binarios con dos nodos y solo un árbol vacío, en el primer caso da dos árboles binarios. El tercero también lo hace. En el segundo caso, los subárboles izquierdo y derecho tienen un nodo, y solo hay un árbol binario con un nodo y por eso hay uno en el segundo. Así pues,en total existen cinco árboles binarios con tres nodos.

Un árbol binario tiene una representación natural en el almacenamiento de listas ligadas.

4) Recorrido de Arboles Binarios

El modo evidente de moverse a través de las ramas de un árbol es siguiendo los punteros, del mismo modo en que nos movíamos a través de las listas. Esos recorridos dependen en gran medida del tipo y propósitodel árbol, pero hay ciertos recorridos que usaremos frecuentemente. Se trata de aquellos recorridos que incluyen todo el árbol.
Hay tres formas de recorrer un árbol completo, y las tres se suelen implementar mediante recursividad. En los tres casos se sigue siempre a partir de cada nodo todas las ramas una por una.

Supongamos que tenemos un árbol de orden tres, y queremos recorrerlo porcompleto.

Partiremos del nodo raíz:

RecorrerArbol(raiz);

La función RecorrerArbol, aplicando recursividad, será tan sencilla como invocar de nuevo a la función RecorrerArbol para cada una de las ramas:

void RecorrerArbol (Arbol a) {
if(a == NULL) return;
RecorrerArbol(a->rama[0]);
RecorrerArbol(a->rama[1]);
RecorrerArbol(a->rama[2]);
}

Lo que diferencia los distintosmétodos de recorrer el árbol no es el sistema de hacerlo, sino el momento que elegimos para procesar el valor de cada nodo con relación a los recorridos de cada una de las ramas.

Los tres tipos son:
Pre-orden:
En este tipo de recorrido, el valor del nodo se procesa antes de recorrer las ramas:

void PreOrden (Arbol a) {
if(a == NULL) return;
Procesar(dato);
RecorrerArbol(a->rama[0]);RecorrerArbol(a->rama[1]);
RecorrerArbol(a->rama[2]);
}

Si seguimos el árbol del ejemplo en pre-orden, y el proceso de los datos es sencillamente mostrarlos por pantalla, obtendremos algo así:A B E K F C G L M D H I J N O

In-orden:
En este tipo de recorrido, el valor del nodo se procesa después de recorrer la primera rama y antes de recorrer la última. Esto tiene más sentido en el...