Árboles
Generalidades
Estructura De Datos NO Lineales
Las estructuras dinámicas lineales de datos – listas, pilas y colas – tienen grandes ventajas de flexibilidad sobre las representaciones contiguas; Sin embargo, tienen un punto débil: SON LISTAS SECUENCIALES
EN LAS ESTRUCTURAS DE DATOS NO LINEALES CADA ELEMENTO PUEDE TENER DIFERENTES “SIGUIENTES” ELEMENTOS, QUE INTRODUCEN EL CONCEPTO DE BIFURCACIÓN
Terminología y Representación de un árbol general
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, Descendente, etc.
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 se derivan 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.
- A cada nodo que no es hoja se asocia uno o varios subárboles llamados descendientes (offspring) o hijos. De igual forma 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 la raíz – que no tiene padre.
- Se denomina camino el enlace entre 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 la raíz al nodo específico.
- La altura o profundidad de un árbol es el número máximo de nodos de una rama. Equivale al nivel más alto de los nodos más uno. El peso de un árbol es el número de nodos terminales.
Representación de un árbol con punteros
Árboles Binarios
Generalidades
Un árbol binario es un conjunto finito de cero o más nodos tales que:
- Existe un nodo denominado raíz del árbol.
- Cada nodo puede tener 0, 1 ó 2 subárboles, conocidos como subárbol izquierdo y subárbol derecho.
Ejemplos de árboles binarios
Recorrido de un Árbol
Se denomina recorrido de un árbol al proceso que permite acceder de una sola vez a cada uno de los nodos del árbol. Cuando un árbol se recorre, el conjunto completo de nodos se examina.
Existen muchos modos para recorrer un árbol binario. Por ejemplo existen seis diferentes recorridos generales en un árbol binario, simétrico dos a dos.
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 acciones 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 raíz está primero y en el post-orden el raíz está el último.
Recorrido pre-orden:
- Visitar el raíz.
- Recorrer el subárbol izquierdo en pre-orden.
- Recorrer el subárbol derecho en pre-orden.
Recorrido en-orden:
- Recorrer el subárbol izquierdo en in-orden.
- Visitar el raíz.
- Recorrer el subárbol derecho en in-orden.
Recorrido post-orden:
- Recorrer el subárbol izquierdo en post-orden.
- Recorrer el subárbol derecho en post-orden.
- Visitar el raíz.
Obsérvese que todas estas definiciones tienen naturaleza recursiva. (Recursiva: Función o Procedimiento que se llama a sí mismo)
ÁRBOL BINARIO DE BÚSQUEDA
El árbol Binario de Búsqueda (binary search tree) se construirá teniendo en cuenta las siguientes premisas:
- El primer elemento se utiliza para crear el nodo raíz.
- Los valores del árbol deben ser tales que pueda existir un orden.
- En cualquier nodo todos los valores del subárbol izquierdo del nodo son menores o iguales al valor del nodo. De modo similar, todos los valores del subárbol derecho deben ser mayores que los valores del nodo.
Si estas condiciones se mantienen, es sencillo probar que el recorrido in-orden del árbol produce los valores clasificados por orden.
Supongamos que disponemos de los siguientes datos:
D F E B A C G
Para construir un árbol binario de búsqueda se procede de la siguiente manera:
- Nodo raíz del árbol: D.
- El siguiente elemento se convierte en el descendente derecho, dado que F alfabéticamente es mayor que D.
- A continuación, se compara E con el raíz. Dado que E es mayor que D, pasará a ser un hijo de F y como E < F será el hijo izquierdo.
- El siguiente elemento B se compara con el raíz D y como B < D, y es el primer elemento que cumple esta condición, B será el hijo izquierdo de D.
- Se repiten los pasos hasta el último elemento.
El árbol binario de búsqueda resultante sería:
Búsqueda de un elemento
Insertar un Elemento
Para insertar un elemento en el árbol, se ha de comprobar, en primer lugar, que el elemento no se encuentra en el árbol, ya que en 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 NIL.
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 nodo en función de que su valor sea inferior o superior al del nodo alcanzado.
Eliminación de un elemento
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 una hoja se suprime simplemente y se marca nulo en el padre.
- Si el elemento no tiene más que un descendiente, se sustituye entonces este por su 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 uno o dos hijos, y en el caso que sea solo uno, si es hijo izquierdo o derecho.
Casos posibles de eliminación de un nodo
Eliminación de un nodo con un subárbol
Eliminación de un nodo con dos subárboles no nulos
Implementación de las funciones con punteros
//Declaraciones generales
Estructura tipo_nombre
…………..
…………..
tipo_nombre izq, der
Fin de estructura
tipo_nombre à elemento, aux, cabecera,ant,aux2,ant2
lógica función buscar(elemento)
ant=NULL
aux = cabecera
mientras(aux)
si(elemento=aux->elemento)
retornar(verdadero)
si no
ant=aux
si(elemento>aux->elemento)
aux=aux->der
si no
aux=aux->izq
fin si
fin si
fin mientras
retornar(falso)
fin función
funcion insertar(elemento)
si (!buscar(elemento))
aux=reservar(tipo_dato)
aux->elemento=elemento
si(elemento>ant->elemento)
ant->der=aux
si no
ant->izq=aux
fin si
fin si
fin funcion
funcion buscmenmay
aux2=aux->der;
ant2=aux;
mientras(aux2->izq)
ant2=aux2;
aux2=aux->izq;
fin mientras
aux->elemento=aux2->elemento
liberar(aux2)
ant2->izq=NULL
fin funcion
funcion buscmaymen
aux2=aux->izq;
ant2=aux;
mientras(aux2->der)
ant2=aux2;
aux2=aux->der;
fin mientras
aux->elemento=aux2->elemento
liberar(aux2)
ant2->der=NULL
fin funcion
funcion eliminar(elemento)
buscar(elemento) //en aux esta elemento
si(aux->der==NULL && aux->izq==NULL)
si(ant->elemento>elemento)
ant->izq=NULL
sino
ant->der=NULL
fin si
eliminar(aux)
sino
si(aux->der!=NULL)
buscmenmay
sino
buscmaymen
fin si
fin si
fin funcion
Ejemplo de Arbol:
#include <iostream.h>
#include <conio.h>
struct arbol
{
int dato;
arbol *i,*d;
}*elemento, *aux, *cabecera, *ant, *aux2, *ant2;
int dato;
int buscar(void);
void insertar(void);
void buscarmenmay(void);
void buscarmaymen(void);
void eliminar(void);
void main(void)
{
int y,opc;
do
{
clrscr();
y=10;
gotoxy(10,y++);
cout<<"0 - Salir";
gotoxy(10,y++);
cout<<"1 - Buscar";
gotoxy(10,y++);
cout<<"2 - Insertar";
gotoxy(10,y);
cout<<"3 - Borrar";
gotoxy(10,y+=5);
cout<<"Cual es su opcion: ";
cin>>opc;
switch(opc)
{
case 0: break;
case 1: cout<<"\n\nDato a buscar: ";
cin>>dato;
if(buscar())
cout<<"\n\nDato existe";
else
cout<<"\n\nDato inexistente";
break;
case 2: cout<<"\n\nDato a insertar: ";
cin>>dato;
insertar();
cout<<"\n\nDato Insertado";
break;
case 3: cout<<"\n\nDato a borrar: ";
cin>>dato;
eliminar();
break;
default: cout<<"\n\nOpcion incorrecta";
}
if(opc) getch();
}while(opc);
}
int buscar(void)
{
if(!cabecera)
{
cout<<"No hay arbol";
return(0);
}
ant=NULL;
aux=cabecera;
while(aux)
{
if (dato==aux->dato)
return(1);
else
{
ant=aux;
if (dato>aux->dato)
aux=aux->d;
else
aux=aux->i;
}
}
return(0);
}
void insertar(void)
{
if(!cabecera)
{
cabecera=new(arbol);
cabecera->dato=dato;
cabecera->d=NULL;
cabecera->i=NULL;
return;
}
if (!buscar())
{
aux=new(arbol);
aux->dato=dato;
aux->i=NULL;
aux->d=NULL;
if(dato>ant->dato)
ant->d=aux;
else
ant->i=aux;
}
else
cout<<"\n\nDato existente";
}
void buscarmenmay(void)
{
aux2=aux->d;
ant2=aux;
while(aux2->i)
{
ant2=aux2;
aux2=aux2->i;
}
aux->dato=aux2->dato;
if(aux2->d)
ant2->i=aux2->d;
delete(aux2);
ant2->d=NULL;
}
void buscarmaymen(void)
{
aux2=aux->i;
ant2=aux;
while(aux2->d)
{
ant2=aux2;
aux2=aux2->d;
}
aux->dato=aux2->dato;
if(aux2->i)
ant2->d=aux2->i;
delete(aux2);
ant2->i=NULL;
}
void eliminar(void)
{
if(!buscar())
{
cout<<"\n\nElemento no encontrado.";
return;
}
if(aux->d==NULL && aux->i==NULL)
{
if(ant->dato>dato)
ant->i=NULL;
else
ant->d=NULL;
delete(aux);
}
else
if(aux->d!=NULL)
buscarmenmay();
else
buscarmaymen();
cout<<"\n\nElemento Borrado";
}