Arboles en C++

| 2013-04-27 | No hay comentarios »

Á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

a1

EN LAS ESTRUCTURAS DE DATOS NO LINEALES CADA ELEMENTO PUEDE TENER DIFERENTES “SIGUIENTES” ELEMENTOS, QUE INTRODUCEN EL CONCEPTO DE BIFURCACIÓN

a2

Terminología y Representación de un árbol general

a3

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

a4

Á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

a5

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:

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

Recorrido en-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.

Obsérvese que todas estas definiciones tienen naturaleza recursiva. (Recursiva: Función o Procedimiento que se llama a sí mismo)

a6

Á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.

a7

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:

  1. Nodo raíz del árbol: D.
  2. El siguiente elemento se convierte en el descendente derecho, dado que F alfabéticamente es mayor que D.
  3. 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.
  4. 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.
  5. Se repiten los pasos hasta el último elemento.

El árbol binario de búsqueda resultante sería:

a8

Búsqueda de un elemento

a9

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.

a10

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

a11

Eliminación de un nodo con un subárbol

a12

Eliminación de un nodo con dos subárboles no nulos

a13

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";
 }

Acerca del autor: Rodrigo Paszniuk

Ingeniero Informático, amante de la tecnología, la música, el ciclismo y aprender cosas nuevas.