ÁRBOLES
DEFINICIÓN
Un árbol es una estructura no lineal formada por un conjunto de nodos y un conjunto de ramas.
En un árbol existe un nodo especial denominado raíz. Así mismo, un nodo del que sale alguna rama, recibe el nombre de Nodo de bifurcación o nodo rama y un nodo que no tiene ramas recibe el nombre nodo terminal o Nodo hoja.
El nivel de un nodo respecto al nodo al nodo raíz se define diciendo que la raíz tiene nivel 0 y cualquier otro nodo tiene un nivel igual a la distancia de ese nodo al nodo raíz. El máximo de los niveles se denomina profundidad o altura del árbol.
Arboles binarios.
Un árbol binario es un conjunto finito de nodos que consta de un nodo raíz que tiene dos subárboles binarios denominados subárbol izquierdo y subárbol derecho.
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'.
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'.
Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama á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', nivel 3.
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.
El árbol binario es una estructura de datos muy útil cuando:
- El tamaño de la estructura no se conoce.
- Se necesita acceder a sus elementos ordenadamente.
- La velocidad de búsqueda es importante.
- El orden en el que se insertan los elementos es casi aleatorio.
CARACTERÍSTICAS
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.
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.
TIPOS DE ÁRBOLES
Es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.
Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura).
A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.
Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.
ÁRBOLES BINARIOS
Un árbol binario puede declararse de varias maneras. Algunas de ellas son:
Estructura con manejo de memoria dinámica, siendo puntA el puntero que apunta al árbol de tipo tArbol:
typedef struct nodo {
int clave;
struct nodo *izdo, *dcho;
}Nodo;
Estructura con arreglo indexado
typedef struct tArbol {
int clave;
tArbol hIzquierdo, hDerecho;
} tArbol;
tArbol árbol[NUMERO_DE_NODOS];
IMPLEMENTACIÓN EN C
En el caso de un árbol binario casi-completo (o un árbol completo), puede utilizarse un sencillo arreglo de enteros con tantas posiciones como nodos deba tener el árbol. La información de la ubicación del nodo en el árbol es implícita a cada posición del arreglo. Así, si un nodo está en la posición i, sus hijos se encuentran en las posiciones 2i+1 y 2i+2, mientras que su padre (si tiene), se encuentra en la posición truncamiento((i-1)/2) (suponiendo que la raíz está en la posición cero). Este método se beneficia de un almacenamiento más compacto y una mejor localidad de referencia, particularmente durante un recorrido en pre-orden.
ÁRBOL BINARIO DE BÚSQUEDA AUTO-BALANCEABLE
Es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente. Esto es importante, ya que muchas operaciones en un árbol de búsqueda binaria tardan un tiempo proporcional a la altura del árbol, y los árboles binarios de búsqueda ordinarios pueden tomar alturas muy grandes en situaciones normales, como cuando las claves son insertadas en orden. Mantener baja la altura se consigue habitualmente realizando transformaciones en el árbol, como la rotación de árboles, en momentos clave.
ÁRBOL MULTICAMINO
Un árbol multicamino posee un grado g mayor a dos, donde cada nodo de información del árbol tiene un máximo de g hijos.
Sea un árbol de m-caminos A, es un árbol m-caminos si y solo si:
ØA está vacío
ØCada nodo de A muestra la siguiente estructura: [nClaves,Enlace0,Clave1,...,ClavenClaves,EnlacenClaves]
ØnClaves es el número de valores de clave de un nodo, pudiendo ser: 0 <= nClaves <= g-1Enlacei, son los enlaces a los subárboles de A, pudiendo ser: 0 <= i <= nClavesClavei, son los valores de clave, pudiendo ser: 1 <= i <= nClavesClavei < Clavei+1
ØCada valor de clave en el subárbol Enlacei es menor que el valor de Clavei+1
ØLos subárboles Enlacei, donde 0 <= i <= nClaves, son también árboles m-caminos.
EJEMPLOS
Ejemplos en C…
//Nodo de un árbol binario
Ejemplo#1
Para C, y basándonos en la declaración de nodo que hemos visto más arriba, trabajaremos con los siguientes tipos:
typedef struct _nodo \{
int dato;
struct _nodo *rama[ORDEN];
} tipoNodo;
typedef tipoNodo *pNodo;
typedef tipoNodo *Arbol;
Declaramos un tipo tipoNodo para declarar nodos, y un tipo pNodo para es el tipo para declarar punteros a un nodo.
Árbol es el tipo para declarar árboles de orden ORDEN.
Ejemplo #2
/* Arbol Binario de Búsqueda en C */
/* (C) Abril 2002, Salvador Pozo */
/* C con Clase: http://c.conclase.net */
#include <stdlib.h>
#include <stdio.h>
#define TRUE 1
#define FALSE 0
/* Estructuras y tipos */
typedef struct _nodo {
int dato;
struct _nodo *derecho;
struct _nodo *izquierdo;
} tipoNodo;
typedef tipoNodo *pNodo;
typedef tipoNodo *Arbol;
/* Funciones con árboles: */
/* Insertar en árbol ordenado: */
void Insertar(Arbol *a, int dat);
/* Borrar un elemento: */
void Borrar(Arbol *a, int dat);
/* Función de búsqueda: */
int Buscar(Arbol a, int dat);
/* Comprobar si el árbol está vacío: */
int Vacio(Arbol r);
/* Comprobar si es un nodo hoja: */
int EsHoja(pNodo r);
/* Contar número de nodos: */
int NumeroNodos(Arbol a, int* c);
/* Calcular la altura de un árbol: */
int AlturaArbol(Arbol a, int* altura);
/* Calcular altura de un dato: */
int Altura(Arbol a, int dat);
/* Aplicar una función a cada elemento del árbol: */
void InOrden(Arbol, void (*func)(int*));
void PreOrden(Arbol, void (*func)(int*));
void PostOrden(Arbol, void (*func)(int*));
/* Funciones auxiliares: */
void Podar(Arbol *a);
void auxContador(Arbol a, int*);
void auxAltura(Arbol a, int, int*);
void Mostrar(int *d);
/* Programa de ejemplo */
int main()
{
Arbol ArbolInt=NULL;
int altura;
int nnodos;
/* Inserción de nodos en árbol: */
Insertar(&ArbolInt, 10);
Insertar(&ArbolInt, 5);
Insertar(&ArbolInt, 12);
Insertar(&ArbolInt, 4);
Insertar(&ArbolInt, 7);
Insertar(&ArbolInt, 3);
Insertar(&ArbolInt, 6);
Insertar(&ArbolInt, 9);
Insertar(&ArbolInt, 8);
Insertar(&ArbolInt, 11);
Insertar(&ArbolInt, 14);
Insertar(&ArbolInt, 13);
Insertar(&ArbolInt, 2);
Insertar(&ArbolInt, 1);
Insertar(&ArbolInt, 15);
Insertar(&ArbolInt, 10);
Insertar(&ArbolInt, 17);
Insertar(&ArbolInt, 18);
Insertar(&ArbolInt, 16);
printf("Altura de arbol %d\n", AlturaArbol(ArbolInt, &altura));
//Mostrar el árbol en tres ordenes distintos:
printf("InOrden: ");
InOrden(ArbolInt, Mostrar);
printf("\n");
printf("PreOrden: ");
PreOrden(ArbolInt, Mostrar);
printf("\n");
printf("PostOrden: ");
PostOrden(ArbolInt, Mostrar);
printf("\n");
/* Borraremos algunos elementos: */
printf("N nodos: %d\n", NumeroNodos(ArbolInt, &nnodos));
Borrar(&ArbolInt, 5);
printf("Borrar 5: ");
InOrden(ArbolInt, Mostrar);
printf("\n");
Borrar(&ArbolInt, 8);
printf("Borrar 8: ");
InOrden(ArbolInt, Mostrar);
printf("\n");
Borrar(&ArbolInt, 15);
printf("Borrar 15: ");
InOrden(ArbolInt, Mostrar);
printf("\n");
Borrar(&ArbolInt, 245);
printf("Borrar 245: ");
InOrden(ArbolInt, Mostrar);
printf("\n");
Borrar(&ArbolInt, 4);
printf("Borrar 4: ");
InOrden(ArbolInt, Mostrar);
printf("\n");
Borrar(&ArbolInt, 17);
printf("Borrar 17: ");
InOrden(ArbolInt, Mostrar);
printf("\n");
/* Veamos algunos parámetros */
printf("N nodos: %d\n", NumeroNodos(ArbolInt, &nnodos));
printf("Altura de 1 %d\n", Altura(ArbolInt, 1));
printf("Altura de 10 %d\n", Altura(ArbolInt, 10));
printf("Altura de arbol %d\n", AlturaArbol(ArbolInt, &altura));
/* Liberar memoria asociada al árbol: */
Podar(&ArbolInt);
system("PAUSE");
return 0;}
/* Poda: borrar todos los nodos a partir de uno, incluido */
void Podar(Arbol *a)
{
/* Algoritmo recursivo, recorrido en postorden */
if(*a) {
Podar(&(*a)->izquierdo); /* Podar izquierdo */
Podar(&(*a)->derecho); /* Podar derecho */
free(*a); /* Eliminar nodo */
*a = NULL;
}
}
/* Insertar un dato en el árbol ABB */
void Insertar(Arbol *a, int dat)
{
pNodo padre = NULL;
pNodo actual = *a;
/* Buscar el dato en el árbol, manteniendo un puntero al nodo padre */
while(!Vacio(actual) && dat != actual->dato) {
padre = actual;
if(dat < actual->dato) actual = actual->izquierdo;
else if(dat > actual->dato) actual = actual->derecho;
}
/* Si se ha encontrado el elemento, regresar sin insertar */
if(!Vacio(actual)) return;
/* Si padre es NULL, entonces el árbol estaba vacío, el nuevo nodo será
el nodo raiz */
if(Vacio(padre)) {
*a = (Arbol)malloc(sizeof(tipoNodo));
(*a)->dato = dat;
(*a)->izquierdo = (*a)->derecho = NULL;
}
/* Si el dato es menor que el que contiene el nodo padre, lo insertamos
en la rama izquierda */
else if(dat < padre->dato) {
actual = (Arbol)malloc(sizeof(tipoNodo));
padre->izquierdo = actual;
actual->dato = dat;
actual->izquierdo = actual->derecho = NULL;
}
/* Si el dato es mayor que el que contiene el nodo padre, lo insertamos
en la rama derecha */
else if(dat > padre->dato) {
actual = (Arbol)malloc(sizeof(tipoNodo));
padre->derecho = actual;
actual->dato = dat;
actual->izquierdo = actual->derecho = NULL;
}}
/* Eliminar un elemento de un árbol ABB */
void Borrar(Arbol *a, int dat)
{
pNodo padre = NULL;
pNodo actual;
pNodo nodo;
int aux;
actual = *a;
/* Mientras sea posible que el valor esté en el árbol */
while(!Vacio(actual)) {
if(dat == actual->dato) { /* Si el valor está en el nodo actual */
if(EsHoja(actual)) { /* Y si además es un nodo hoja: lo borramos */
if(padre) /* Si tiene padre (no es el nodo raiz) */
/* Anulamos el puntero que le hace referencia */
if(padre->derecho == actual) padre->derecho = NULL;
else if(padre->izquierdo == actual)}
padre->izquierdo = NULL;
free(actual); /* Borrar el nodo */
actual = NULL;
return;
}
else { /* Si el valor está en el nodo actual, pero no es hoja */
padre = actual;
/* Buscar nodo más izquierdo de rama derecha */
if(actual->derecho) {
nodo = actual->derecho;
while(nodo->izquierdo) {
padre = nodo;
nodo = nodo->izquierdo;
}
}
/* O buscar nodo más derecho de rama izquierda */
else {
nodo = actual->izquierdo;
while(nodo->derecho) {
padre = nodo;
nodo = nodo->derecho;
}
}
/* Intercambiar valores de no a borrar u nodo encontrado
y continuar, cerrando el bucle. El nodo encontrado no tiene
por qué ser un nodo hoja, cerrando el bucle nos aseguramos
de que sólo se eliminan nodos hoja. */
aux = actual->dato;
actual->dato = nodo->dato;
nodo->dato = aux;
actual = nodo;
}
}
else { /* Todavía no hemos encontrado el valor, seguir buscándolo */
padre = actual;
if(dat > actual->dato) actual = actual->derecho;
else if(dat < actual->dato) actual = actual->izquierdo;
}
}
}
/* Recorrido de árbol en inorden, aplicamos la función func, que tiene
el prototipo:
void func(int*);
*/
void InOrden(Arbol a, void (*func)(int*))
{
if(a->izquierdo) InOrden(a->izquierdo, func);
func(&(a->dato));
if(a->derecho) InOrden(a->derecho, func);
}
/* Recorrido de árbol en preorden, aplicamos la función func, que tiene
el prototipo:
void func(int*);
*/
void PreOrden(Arbol a, void (*func)(int*))
{
func(&a->dato);
if(a->izquierdo) PreOrden(a->izquierdo, func);
if(a->derecho) PreOrden(a->derecho, func);
}
/* Recorrido de árbol en postorden, aplicamos la función func, que tiene
el prototipo:
void func(int*);
*/
void PostOrden(Arbol a, void (*func)(int*))
{
if(a->izquierdo) PostOrden(a->izquierdo, func);
if(a->derecho) PostOrden(a->derecho, func);
func(&a->dato);
}
/* Buscar un valor en el árbol */
int Buscar(Arbol a, int dat)
{
pNodo actual = a;
/* Todavía puede aparecer, ya que quedan nodos por mirar */
while(!Vacio(actual)) {
if(dat == actual->dato) return TRUE; /* dato encontrado */
else if(dat < actual->dato) actual = actual->izquierdo; /* Seguir */
else if(dat > actual->dato) actual = actual->derecho;
}
return FALSE; /* No está en árbol */
}
/* Calcular la altura del nodo que contiene el dato dat */
int Altura(Arbol a, int dat)
{
int altura = 0;
pNodo actual = a;
/* Todavía puede aparecer, ya que quedan nodos por mirar */
while(!Vacio(actual)) {
if(dat == actual->dato) return altura; /* encontrado: devolver altura */
else {
altura++; /* Incrementamos la altura, seguimos buscando */
if(dat < actual->dato) actual = actual->izquierdo;
else if(dat > actual->dato) actual = actual->derecho;
}
}
return -1; /* No está en árbol, devolver -1 */
}
/* Contar el número de nodos */
int NumeroNodos(Arbol a, int *contador)
{
*contador = 0;
auxContador(a, contador); /* Función auxiliar */
return *contador;
}
/* Función auxiliar para contar nodos. Función recursiva de recorrido en
preorden, el proceso es aumentar el contador */
void auxContador(Arbol nodo, int *c)
{
(*c)++; /* Otro nodo */
/* Continuar recorrido */
if(nodo->izquierdo) auxContador(nodo->izquierdo, c);
if(nodo->derecho) auxContador(nodo->derecho, c);
}
/* Calcular la altura del árbol, que es la altura del nodo de mayor altura. */
int AlturaArbol(Arbol a, int *altura)
{
*altura = 0;
auxAltura(a, 0, altura); /* Función auxiliar */
return *altura;}
/* Función auxiliar para calcular altura. Función recursiva de recorrido en
postorden, el proceso es actualizar la altura sólo en nodos hojas de mayor
altura de la máxima actual */
void auxAltura(pNodo nodo, int a, int *altura)
{
/* Recorrido postorden */
if(nodo->izquierdo) auxAltura(nodo->izquierdo, a+1, altura);
if(nodo->derecho) auxAltura(nodo->derecho, a+1, altura);
/* Proceso, si es un nodo hoja, y su altura es mayor que la actual del
árbol, actualizamos la altura actual del árbol */
if(EsHoja(nodo) && a > *altura) *altura = a;
}
/* Comprobar si un árbol es vacío */
int Vacio(Arbol r)
{
return r==NULL;
}
/* Comprobar si un nodo es hoja */
int EsHoja(pNodo r)
{
return !r->derecho && !r->izquierdo;
}
/* Función de prueba para recorridos del árbol */
void Mostrar(int *d)
{
printf("%d, ", *d);
}
No hay comentarios:
Publicar un comentario