tipos de àrboles

Un árbol es una estructura de datos ampliamente usada que imita 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 más nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde 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. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.
También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles.
Esto son definiciones simples. Pero las características que implican no lo son tanto.
Definiremos varios conceptos. En relación con otros nodos:
Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.
Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.

Los árboles con los que trabajaremos tienen otra característica importante: cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles.
En cuanto a la posición dentro del árbol:

Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.

Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.
Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.

Otra característica que normalmente tendrán nuestros árboles es que todos los nodos contengan el mismo número de punteros, es decir, usaremos la misma estructura para todos los nodos del árbol. Esto hace que la estructura sea más sencilla, y por lo tanto también los programas para trabajar con ellos.

Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que pueden usarse todos, algunos o ninguno de los punteros de cada nodo.
Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo.

En una cosa, los árboles se parecen al resto de las estructuras que hemos visto: dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente. Es decir, un nodo cualquiera puede ser considerado como la raíz de un árbol completo.
Existen otros conceptos que definen las características del árbol, en relación a su tamaño:

Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc.

Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos.

Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N',

Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.

Los árboles de orden dos son bastante especiales, de hecho les dedicaremos varios capítulos. Estos árboles se conocen también como árboles binarios.
Frecuentemente, aunque tampoco es estrictamente necesario, para hacer más fácil moverse a través del árbol, añadiremos un puntero a cada nodo que apunte al nodo padre. De este modo podremos avanzar en dirección a la raíz, y no sólo hacia las hojas.
Es importante conservar siempre el nodo raíz ya que es el nodo a partir del cual se desarrolla el árbol, si perdemos este nodo, perderemos el acceso a todo el árbol.
El nodo típico de un árbol difiere de los nodos que hemos visto hasta ahora para listas, aunque sólo en el número de nodos. Veamos un ejemplo de nodo para crear árboles de orden tres:
struct nodo {
int dato;
struct nodo *rama1;
struct nodo *rama2;
struct nodo *rama3;
};
O generalizando más:
#define ORDEN 5

struct nodo {
int dato;
struct nodo *rama[ORDEN];
};

Formalmente, podemos definir un árbol de la siguiente forma:

Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).
Un nuevo árbol a partir de un nodo mr. y k árboles de raíces con elementos cada uno, puede construirse estableciendo una relación padre-hijo entre nr y cada una de las raíces de los k árboles. El árbol resultante de nodos tiene como raíz el nodo nr, los nodos son los hijos de nr y el conjunto de nodos hoja está formado por la unión de los k conjuntos hojas iniciales. A cada uno de los árboles Ai se les denota ahora subárboles de la raíz.

Una sucesión de nodos del árbol, de forma que entre cada dos nodos consecutivos de la sucesión haya una relación de parentesco, decimos que es un recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero en anchura. En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y así sucesivamente. En el segundo, por su parte, antes de listar los nodos de nivel n + 1 (a distancia n + 1 aristas de la raíz), se deben haber listado todos los de nivel n. Otros recorridos típicos del árbol son preorden, postorden e inorden:

El recorrido en preorden, también llamado orden previo consiste en recorrer en primer lugar la raíz y luego cada uno de los hijos en orden previo.
El recorrido en inorden, también llamado orden simétrico (aunque este nombre sólo cobra signDefinición de árbol

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 (ver grafos): 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 esta sección no se tratará esta implementación.

Clasificación de Arboles Binarios
Existen cuatro tipos de árbol binario:.
· Arbol Binario Distinto.
· Arbol Binario Similares.
· Arbol Binario Equivalentes.
· Arbol Binario Completos.

A continuación se hará una breve descripción de los diferentes tipos de árbol binario así como un ejemplo de cada uno de ellos.

Arbol Binario Distinto
Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes.
Ejemplo:

Arbol Binario Similar
Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente.
Ejemplo:

Arbol Binario Equivalente
Son aquellos arboles que son similares y que además los nodos contienen la misma información. Ejemplo:

Arbol Binario Completo
Son aquellos arboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subárbol izquierdo y el subárbol derecho.

Arboles Binarios
Se define un árbol binario como un conjunto finito de elementos (nodos) que bien esta vacío o esta formado por una raíz con dos arboles binarios disjuntos, es decir, dos descendientes directos llamados subárbol izquierdo y subárbol derecho.
Los árboles binarios (también llamados de grado 2 )tienen una especial importancia.
Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.

Árbol binario de búsqueda.
Los árboles binarios se utilizan frecuentemente para representar conjuntos de datos cuyos elementos se identifican por una clave única. Si el árbol está organizado de tal manera que la clave de cada nodo es mayor que todas las claves su subárbol izquierdo, y menor que todas las claves del subárbol derecho se dice que este árbol es un árbol binario de búsqueda.
Ejemplo:

Operaciones básicas
Una tarea muy común a realizar con un árbol es ejecutar una determinada operación con cada uno de los elementos del árbol. Esta operación se considera entonces como un parámetro de una tarea más general que es la visita de todos los nodos o, como se denomina usualmente, del recorrido del árbol.
Si se considera la tarea como un proceso secuencial, entonces los nodos individuales se visitan en un orden específico, y pueden considerarse como organizados según una estructura lineal. De hecho, se simplifica considerablemente la descripción de muchos algoritmos si puede hablarse del proceso del siguiente elemento en el árbol, según un cierto orden subyacente.
Hay dos formas básicas de recorrer un árbol: El recorrido en amplitud y el recorrido en profundidad.

Recorrido de un Árbol Binario
Recorrido en amplitud
Es aquel recorrido que recorre el árbol por niveles, en el último ejemplo sería:
12 - 8,17 - 5, 9,15

Recorrido en profundidad
Recorre el árbol por subárboles.
Hay tres Pre orden, orden central y postor den.
Hay tres formas: en inorden, preorden y postorden. Cada una de ellas tiene una secuencia distinta para analizar el árbol como se puede ver a continuación:

1. Inorden
· Recorrer el subárbol izquierdo en inorden.
· Examinar la raíz.
· Recorrer el subárbol derecho en inorden.

Preorden
· Examinar la raíz.
· Recorrer el subárbol izquierdo en preorden.
· recorrer el subarbol derecho en preorden.

Postorden
· Recorrer el subarbol izquierdo en postorden.
· Recorrer el subárbol derecho en postor den.
· Examinar la raíz.

A continuación se muestra un ejemplo de los diferentes recorridos en un árbol binario.
Inorden: GDBHEIACJKF
Preorden: ABDGEHICFJK
Postorden: GDHIEBKJFCA
Clasificación de Arboles Binarios
Existen cuatro tipos de árbol binario:.
· Árbol Binario Distinto.
· Árbol Binario Similares.
· Árbol Binario Equivalentes.
· Árbol Binario Completos.
A continuación se hará una breve descripción de los diferentes tipos de árbol binario así como un ejemplo de cada uno de ellos.

Árbol Binario Distinto

Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes.
Ejemplo:
Árbol Binario Similar
Dos arboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente.
Ejemplo:

Árbol Binario Equivalente
Son aquellos arboles que son similares y que además los nodos contienen la misma información. Ejemplo:

Árbol Binario Completo
Son aquellos arboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subárbol izquierdo y el subárbol derecho.
Terminología

La terminología que por lo regular se utiliza para el manejo de arboles es la siguiente:
· Hijo: X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.
· Padre: X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y.
· Hermano: Dos nodos serán hermanos si son descendientes directos de un mismo nodo.
· Hoja: Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos).
· Nodo anterior: Es un nodo que no es raíz ni terminal.
· Grado: Es el número de descendientes directos de un determinado nodo.
· Grado de un árbol: Es el máximo grado de todos los nodos del árbol.
· 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.
· Altura: Es el máximo número de niveles de todos los nodos del árbol.
· Peso: Es el número de nodos del árbol sin contar la raíz.
· Longitud de camino: Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente.

OPERACIÓN BASICA SOBRE LOS ARBOLES BINARIOS DE BUSQUEDA

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.boolean buscar(tarbol *a, int elem){ if (a == NULL) return FALSE; else if (a->clave <>der, elem); else if (a->clave > elem) return buscar(a->izq, elem); else return TRUE;}

- INSERCIÓN

La inserción tampoco es complicada. Es más, resulta practicamente idéntica a la búsqueda. Cuando se llega a un árbol vacío se crea el nodo en el puntero que se pasa como parámetro por referencia, de esta manera los nuevos enlaces mantienen la coherencia. Si el elemento a insertar ya existe entonces no se hace nada.void insertar(tarbol **a, int elem){ if (*a == NULL) { *a = (arbol *) malloc(sizeof(arbol)); (*a)->clave = elem; (*a)->izq = (*a)->der = NULL; } else if ((*a)->clave <>der, elem); else if ((*a)->clave > elem) insertar(&(*a)->izq, elem);}

- Borrado

La operación de borrado si resulta ser algo más complicada. Se recuerda que el árbol debe seguir siendo de búsqueda tras el borrado. Pueden darse tres casos, una vez encontrado el nodo a borrar:1) El nodo no tiene descendientes. Simplemente se borra.2) El nodo tiene al menos un descendiente por una sola rama. Se borra dicho nodo, y su primer descendiente se asigna como hijo del padre del nodo borrado. Ejemplo: en el árbol de la figura 5 se borra el nodo cuya clave es

-

1. El árbol resultante es:

3) El nodo tiene al menos un descendiente por cada rama. Al borrar dicho nodo es necesario mantener la coherencia de los enlaces, además de seguir manteniendo la estructura como un árbol binario de búsqueda. La solución consiste en sustituir la información del nodo que se borra por el de una de las hojas, y borrar a continuación dicha hoja. ¿Puede ser cualquier hoja? No, debe ser la que contenga una de estas dos claves:· la mayor de las claves menores al nodo que se borra. Suponer que se quiere borrar el nodo 4 del árbol de la figura 5. Se sustituirá la clave 4 por la clave 2.· la menor de las claves mayores al nodo que se borra. Suponer que se quiere borrar el nodo 4 del árbol de la figura 5. Se sustituirá la clave 4 por la clave 5.
El algoritmo de borrado que se implementa a continuación realiza la sustitución por la mayor de las claves menores, (aunque se puede escoger la otra opción sin pérdida de generalidad). Para lograr esto es necesario descender primero a la izquierda del nodo que se va a borrar, y después avanzar siempre a la derecha hasta encontrar un nodo hoja. A continuación se muestra gráficamente el proceso de borrar el nodo de clave 4:

Codificación: el procedimiento sustituir es el que desciende por el árbol cuando se da el caso del nodo con descencientes por ambas ramas.void borrar(tarbol **a, int elem){ void sustituir(tarbol **a, tarbol **aux); tarbol *aux; if (*a == NULL) /* no existe la clave */ return; if ((*a)->clave <>der, elem); else if ((*a)->clave > elem) borrar(&(*a)->izq, elem); else if ((*a)->clave == elem) { aux = *a; if ((*a)->izq == NULL) *a = (*a)->der; else if ((*a)->der == NULL) *a = (*a)->izq; else sustituir(&(*a)->izq, &aux); /* se sustituye por la mayor de las menores */ free(aux); }}


CONSTRUCCIÓN DE UN ÁRBOL BINARIO
Hasta el momento se ha visto la declaración y recorrido de un árbol binario. Sin embargo no se ha estudiado ningún método para crearlos. A continuación se estudia un método para crear un árbol binario que no tenga claves repetidas partiendo de su recorrido en preorden e inorden, almacenados en sendos arrays.
Antes de explicarlo se recomienda al lector que lo intente hacer por su cuenta, es sencillo cuando uno es capaz de construir el árbol viendo sus recorridos pero sin haber visto el árbol terminado.
Partiendo de los recorridos preorden e inorden del árbol de la figura 1 puede determinarse que la raíz es el primer elemento del recorrido en preorden. Ese elemento se busca en el array inorden. Los elementos en el array inorden entre izq y la raíz forman el subárbol izquierdo. Asimismo los elementos entre der y la raíz forman el subárbol derecho. Por tanto se tiene este árbol:


A continuación comienza un proceso recursivo. Se procede a crear el subárbol izquierdo, cuyo tamaño está limitado por los índices izq y der. La siguiente posición en el recorrido en preorden es la raíz de este subárbol. Queda esto:


El subárbol b tiene un subárbol derecho, que no tiene ningún descendiente, tal y como indican los índices izq y der. Se ha obtenido el subárbol izquierdo completo de la raíz a, puesto que b no tiene subárbol izquierdo:

REFERENCIAS:

http://www.conclase.net/c/edd/index.php?cap=006
http://www.algoritmia.net/articles.php?id=17
http://contrerasquintero.com/EDD/5.2.4.HTML
co.com/ http://www.mitecnologico.com/Main/EliminacionArbolesBinarios