Arbol binario
Estructura recursiva, que consta de un elemento denominado raíz , que contiene un campo de
información genérico y dos árboles binarios asociados, llamados subárbol derecho y subárbol
izquierdo.
typedef struct NodoArbin
{
TipoA info;
struct NodoArbin *izq ,*der;
}TArbin,*Arbin;
Una de las ventajas de los arboles binarios, es la optimización de la búsqueda de
elementos, gracias a que usa una regla para insertar ordenadamente elementos.
Propiedades :
El elemento de la raíz del subárbol izquierdo es menor que la raíz.
El elemento de la raíz del subárbol derecho es mayor que la raíz.
Para insertar se implementa un función recursiva , que recorre el árbol hasta encontrar
el subárbol indicado para insertar.
Ya que el tipo de información que contienen los nodos del árbol binario son genéricos (TipoA) ,
es necesario pasar como parámetro el criterio de comparación, que resuelve si un elemento de tipo TipoA es
mayor que otro del mismo tipo.
Una de las técnicas conocidas para resolver estos problemas, es usar los punteros a funciones.
Ejemplo :
Se quiere almacenar en un árbol la información de un producto determinado , que consta de las
siguientes características : código , precio y cantidad.
Se pide almacenar ordenadamente según el precio y la cantidad.
Solución :
Lo primero que debemos hacer es declarar una estructura que almacene los tres campos.
typedef struct
{
int codigo;
double precio;
int cantidad;
} PRODUCTO;
Luego, declaramos que TipoA , va a ser de tipo PRODUCTO.
typedef PRODUCTO TipoA;
Ahora, nos preocupamos del asunto de los criterios de almacenamiento. Nos dicen que
comparemos por precio y cantidad. Por lo tanto tenemos que hacer dos funciones de
comparación que nos indiquen si un elemento de tipo PRODUCTO es mayor que otro , según
sus campos.
int mayor_precio(PRODUCTO a , PRODUCTO b)
{
return a.precio > b.precio;
}
int mayor_cantidad(PRODUCTO a , PRODUCTO b)
{
return a.cantidad > b.cantidad;
}
Después de esto, sólo tenemos que pasar las funciones anteriores como parámetro
a la función insertar.
Funciones del TAD
Arbin arbinVacio(void) : Crea un árbol vacío. Advertencia : Usar siempre antes de
insertar datos en un árbol que no tenga datos. No hacerlo puede provocar errores.
Arbin crearArbin(TipoA info) : Crea una variable de
tipo Arbin , con los dos subárboles nulos.
Arbin insertarArbin(Arbin a,TipoA elem,int (*func_mayor)(TipoA,TipoA)) : Inserta un elemento
elem en el árbol binario a
bajo el criterio de comparación pasado como función.
TipoA raizArbin(Arbin a) : retorna el campo info del nodo a.
int vacioArbin(Arbin a) : retorna 1 si el árbol es vacío.
Arbin izqArbin(Arbin a) : retorna el subárbol izquierdo.
Arbin derArbin(Arbin a) : retorna el subárbol derecho.
Ejemplo
#include<stdio.h>
#include<stdlib.h>
typedef int TipoA;
#include "tadArbin.h"
int mayor(int a , int b)
{
return a > b;
}
int main()
{
/* importante hacer esta asignación , no hacerlo provoca errores !! */
Arbin a = arbinVacio();
a = insertarArbin(a,30,mayor);
a = insertarArbin(a,10,mayor);
a = insertarArbin(a,50,mayor);
printf("\n raiz : %d " , raizArbin(a));
printf("\n izquierdo : %d ", raizArbin( izqArbin(a) ));
printf("\n derecho : %d ", raizArbin( derArbin(a) ));
return 0;
}
Implementación
/* tadArbin.h */
typedef struct NodoArbin
{
TipoA info;
struct NodoArbin *izq,*der;
}TArbin,*Arbin;
Arbin arbinVacio(void)
{
return NULL;
}
Arbin crearArbin(TipoA info)
{
Arbin temp = (Arbin) malloc(sizeof (TArbin));
temp->info = info;
temp->der = temp->izq = NULL;
return temp;
}
Arbin izqArbin(Arbin a)
{
return a->izq;
}
Arbin derArbin(Arbin a)
{
return a->der;
}
TipoA raizArbin(Arbin a)
{
return a->info;
}
int vacioArbin(Arbin a)
{
return a == NULL;
}
Arbin insertarArbin(Arbin a,TipoA elem,int (*func_mayor)(TipoA,TipoA))
{
if (vacioArbin(a)) a = crearArbin(elem);
else
{
TipoA aux = raizArbin(a);
if(func_mayor(elem,aux))
{
if (!vacioArbin(derArbin(a)))
insertarArbin(derArbin(a),elem,func_mayor);
else
a->der = crearArbin(elem);
}
else
{
if (!vacioArbin(izqArbin(a)))
insertarArbin(izqArbin(a),elem,func_mayor);
else
a->izq = crearArbin(elem);
}
}
return a;
}
