pilas
ESTRUCTURA DE DATOS
Una pila es una estructura de datos a la cual se puede acceder solo por un extremo de la misma. Las operaciones de inserción y extracción se realizan a través del tope, por lo cual no se puede acceder a cualquier elemento de la pila. Se le suele llamar estructura L.I.F.O. como acrónimo de las palabras inglesas "last in, first out" (último en entrar, primero en salir). La pila se considera un grupo ordenado de elementos, teniendo en cuenta que el orden de los mismos depende del tiempo que lleven "dentro" de la estructura.
La pila debe pensarse como una resma de hojas sobre un escritorio, con sólo dos posibles operaciones básicas: apilar (agregar o push) y desapilar (sacar o pop). Se agregan hojas una sobre la otra, y se retiran desde arriba hacia abajo. Esto significa que en todo momento, sólo se puede acceder directamente al último elemento agregado (el que está más arriba en la pila, que es llamado TOS).
Pila de llamadas�
Pila como tipo abstracto de datos�
Operaciones�
Implementación�
Un requisito típico de almacenamiento de una pila de n elementos es O(n). El requisito típico de tiempo de O(1) las operaciones también son fáciles de satisfacer con un array o con listas enlazadas simples.
La biblioteca de plantillas de C++ estándar proporciona una "pila" clase templated que se limita a sólo apilar/desapilar operaciones. Java contiene una biblioteca de la clase Pila que es una especialización de Vector. Esto podría ser considerado como un defecto, porque el diseño heredado get () de Vector método LIFO ignora la limitación de la Pila.
Una pila acotada es una pila limitada a un tamaño máximo impuesto en su especificación.
Expresión de evaluación y análisis sintáctico�
Se calcula empleando la notación polaca inversa utilizando una estructura de pila para los posibles valores. Las expresiones pueden ser representadas en prefijo, infijo, postfijo. La conversión de una forma de la expresión a otra forma necesita de una pila. Muchos compiladores utilizan una pila para analizar la sintaxis de las expresiones, bloques de programa, etc. Antes de traducir el código de bajo nivel. La mayoría de los lenguajes de programación son de contexto libre de los idiomas que les permite ser analizados con máquinas basadas en la pila.
Por ejemplo, el cálculo: ((1 + 2) * 4) + 3, puede ser anotado como en notación postfija con la ventaja de no prevalecer las normas y los paréntesis necesario:
1 2 + 4 * 3 +
La expresión es evaluada de izquierda a derecha utilizando una pila:
De la siguiente manera (la Pila se muestra después de que la operación se haya llevado a cabo):
ENTRADA OPERACION PILA
1 Apilar operando 1
2 Apilar operando 1, 2
+ Añadir 3
4 Apilar operando 3, 4
* Multiplicar 12
3 Apilar operando 12, 3
+ Añadir 15
�El resultado final, 15, se encuentra en la parte superior de la pila al final del cálculo.
Ejemplo de pila en C�
Supongamos que queremos construir una pila para almacenar números enteros. Haremos pruebas intercalando varios "push" y "pop", y comprobando el resultado.
Algoritmo de la función "push"
void Push(Pila *pila, int v) \{
pNodo nuevo;
/* Crear un nodo nuevo */
nuevo = (pNodo)malloc(sizeof(tipoNodo));
nuevo->valor = v;
/* Añadimos la pila a continuación del nuevo nodo */
nuevo->siguiente = *pila;
/* Ahora, el comienzo de nuestra pila es en nuevo nodo */
*pila = nuevo;
}
Algoritmo de la función "pop"
int Pop(Pila *pila) \{
pNodo nodo; /* variable auxiliar para manipular nodo */
int v; /* variable auxiliar para retorno */
/* Nodo apunta al primer elemento de la pila */
nodo = *pila;
if(!nodo) return 0; /* Si no hay nodos en la pila retornamos 0 */
/* Asignamos a pila toda la pila menos el primer elemento */
*pila = nodo->siguiente;
/* Guardamos el valor de retorno */
v = nodo->valor;
/* Borrar el nodo */
free(nodo);
return v;
}
COLAS
DEFINICION
Son aquellas que solo tiene 2 operaciones, Push(Inserción) y Pop(Eliminación). Push solo se puede efectuar por un extremo llamado Frente y Pop por el extremo Llamado Final. Sin Embargo se le pueden aplicar todas las operaciónes al igual que a las listas.
RECORRIDO
Ya que las colas son FIFO(First in - First Out) el Recorrido se hace sacando el primer dato que se inserto hasta que llegue al extremo llamado Final.
COMO FUNCIONA:
En un principio se compara para saber si tiene algún dato en la Cola, si no es así desplegara “Cola Vacía…”. De otra forma compara si Frente es mayor o igual a Final, de esta forma simplemente hace un Recorrido lineal como los anteriores. De otra forma usar Max como bandera para saber cuando empezar a contar de 0 a Final (Ya que sabemos que el Frente después del nodo Final).
Algoritmo
Recorrido(Cola, Frente, Final, Max)
Si Frente ≠ Nulo
Si Frente ≤ Final, entonces:
Apuntador <-- Frente
Repetir mientras Apuntador ≤ Final
Imprimir Cola[Apuntador]
Apuntador <-- Apuntador + 1
Fin del ciclo
Si no, si Frente > Final, entonces:
Apuntador <-- Frente
Repetir mientras Apuntador ≠ Final
Si Apuntador > Max, entonces:
Apuntador <-- 0
Imprimir Cola[Apuntador]
Apuntador <-- Apuntador + 1
Fin del ciclo
Si no:
Imprimir "Cola Vacía"
Salir
DIAGRAMA
PUSH
Definición:
Push es simplemente el método por el cual va agregando un Dato nuevo a la Cola tomando en cuenta el Tamaño Máximo de Capacidad (Max), el Frente y el Final de la Cola.
Primero nos aseguramos que la Cola no este Llena, para que de esta manera sea capaz de insertar un Elemento nuevo. Si no desplegara Cola Llena. Después compara para determinar las posiciones de Frente y Final y de esta manera poder moverlo con libertad. Ya que determina los valores de Frente y Final, nos Indica que Cola[Final] tomara el valor de Elemento.
Algoritmo
Push(Cola, Frente, Final, Max, Elemento)
Si Frente = 0 y Final =9, o si Frente = (Final + 1)
Imprimir "Cola Llena" y Salir
Si Frente = Nulo
Frente <-- 0
Final <-- 0
Si no, si Final = Max
Final <-- 0
Si no:
Final <-- Final + 1
Cola[Final] = Elemento
Salir
DIAGRAMA
POP
Definición:
Pop es simplemente el método por el cual va sacando el primer Dato de la Cola (esto se comprueba ya que las Colas son FIFO), para esto toma en cuenta el Frente.
Compara para determinar si la cola esta vacía, de otra forma lo que hace es Imprimir “Eliminando el Dato…”. Después se hacen una series de comparaciones para determinar la nueva posición de Frente, de esa forma el Dato que existía en Frente es Eliminado.
Algoritmo
Pop(Cola, Frente, Final, Max)
Si Frente ≠ Nulo
Imprimir "Eliminado el Dato..."
Si Frente = Final
Frente = Nulo
Final = Nulo
Si no, si Frente = Max
Frente = 0
Si no:
Frente <-- Frente + 1
Si no:
Imprimir "Cola Vacía"
Salir
DIAGRAMA
Busqueda
Definición:
Este método usa el recorrido para encontrar un Elemento y desplegar un mensaje si la búsqueda es exitosa.
El algoritmo usa básicamente la misma estructura del Recorrido, la única diferencia es que compara cada uno de los Datos con Elemento, de esta forma se da cuenta si este Dato existe en la Cola.
Algoritmo
Busqueda(Cola, Frente, Fin, Max, Elemento)
Si Frente ≠ Nulo
Si Frente ≤ Final, entonces:
Apuntador <-- Frente
Repetir mientras Apuntador ≤ Final
Si Elemento = Cola[Apuntador]
Imprimir "Dato encontrado..." y Salir
Apuntador <-- Apuntador + 1
Fin del ciclo
Si no, si Frente > Final, entonces:
Apuntador <-- Frente
Repetir mientras Apuntador ≠ Final
Si Apuntador > Max, entonces:
Apuntador <-- 0
Si Elemento = Cola[Apuntador]
Imprimir "Dato encontrado..." y Salir
Apuntador <-- Apuntador + 1
Fin del ciclo
Imprimir "Dato no encontrado..."
Si no:
Imprimir "Cola Vacía"
Salir
Diagrama
Eliminacion
Definición:
Este método busca un Dato dentro de la cola y lo elimina.
Este Método es la mezcla de todos en uno, Recorrido, Búsqueda, Pop y Push. Debido que a busca el Dato haciendo un Recorrido, y en el proceso copia todos los Datos que no son en un Arreglo Temp, para después meterlos a la Cola original, esto lo hace hasta encontrar el dato deseado que posteriormente lo Elimina.
Diagrama
listas
Tomás Gerónimo Morales
Definición�
caracteristicas
clasificación
Una lista enlazada se puede definir recursivamente de la siguiente manera:�
Implementación
struct lista
{
int clave;
struct lista *sig;
};
Listas ordenadas�
struct lista *L;
L = NULL;
Cabecera ficticia y centinela�
Como se ha observado anteriormente, a la hora de insertar o actualizar elementos en una lista ordenada o reorganizable es fundamental actualizar el primer elemento de la lista cuando sea necesario. Esto lleva un coste de tiempo, aunque sea pequeño salvo en el caso de numerosas inserciones y borrados. Para subsanar este problema se utiliza la cabecera ficticia.
Se declara una lista vacía con cabecera, reservando memoria para la cabecera, de la siguiente manera:
struct lista {
int clave;
struct lista *sig;
}
...
struct lista *L;
L = (struct lista *) malloc(sizeof(struct lista));
L->sig = NULL;
Listas doblemente enlazadas�
Listas circulares�
Las listas circulares son aquellas en las que el último elemento tiene un enlace con el primero. Su uso suele estar relacionado con las colas, y por tanto su desarrollo se realizará en el tema de colas. Por supuesto, se invita al lector a desarrollarlo por su cuenta.
Á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:
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.
CARACTERÍSTICAS
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];
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.
IMPLEMENTACIÓN EN C
Á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:
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);
}
GRAFOS
ESTRUCTURA DE DATOS
Conceptos matemáticos :
Grafo. Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.
Impresora
Modem
PC2
Servidor
PC1
Dado un escenario donde ciertos objetos se relacionan, se puede “modela el grafo” y luego aplicar algoritmos para resolver diversos problemas
DEFINICION
V = {1, 4, 5, 7, 9}
A= {(1,4), (5,1), (7,9), (7,5), (4,9), (4,1), (1,5), (9,7), (5, 7), (9,4)}
1
4
5
7
9
Etiquetado. Distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto, es decir, asignarle a cada vértice o arista un nombre.
Terminología:
Adyacencia. Se dice que dos vértices son adyacentes si hay una arista que los conecte entre ellos.
Grado de un vértice. El grado de un vértice es un número natural de 0 al infinito que designa el número de aristas le conectan con otros vértices.
Incidencia. Una arista es incidente a un vértice si ésta lo une a otro.
Ponderación. Corresponde a una función que a cada arista le asocia un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo.
Camino. Un camino es una secuencia de aristas que comienzan en un vértice del grafo y recorren parte o la totalidad del grafo conectando vértices adyacentes.
Circuito. Cuando existe un camino que empieza y acaba en el mismo vértice.
Isomorfismo. Si dos grafos son isomorfos sólo varía la apariencia, es decir, que se mantienen las adyacencias, estructura, caminos, ciclos, número de vértices y número de aristas.
Conexo. Un grafo es conexo si tiene una única componente conexa, es decir, todos los vértices del grafo están relacionados.
Grafo regular:
Grafo completo:
Grafo complementario:
Grafo bipartito:
Grafo bipartito completo:
Grafo original
Grafo complementario
Familias de grafos simples:
TIPOS DE GRAFOS
C
E
D
F
H
V = {C, D, E, F, H}
A= {(C,D), (D,F), (E,H), (H,E), (E,C)}
1
4
5
7
9
Grafo del ejemplo anterior
OTROS CONCEPTOS
Guayaquil
Quito
Cuenca
Ambato
Riobamba
5
5
7
9
8
7
GRADOS DE UN NODO
C
E
D
F
H
Guayaquil
Quito
Cuenca
Ambato
Riobamba
5
5
7
9
8
7
Gradoent(D) = 1 y Gradsal(D) = 1
Grado(Guayaquil) = 3
CAMINOS
4
7
9
6
10
11
Camino entre 4 y 7
P = {4, 6, 9, 7}
Longitud: 3
A
B
C
D
E
F
Camino A y A
P = {A, E, B, F, A}
Longitud: 4 – 4ciclo
CONECTIVIDAD
3
9
5
7
2
4
5
6
8
H
A
B
D
REPRESENTACION
MATRIZ DE ADYACENCIA
Si el grafo fuese valorado, en vez de 1, se coloca el factor de peso
4
7
9
6
10
11
V0
V1
V2
V3
V4
V5
EL TIPO DE DATO
LISTA DE ADYACENCIA
4
7
9
6
10
11
4
6
9
7
10
11
6
4
6
9
11
10
9
7
EL TIPO DE DATO
RECORRIDOS DEL GRAFO
RECORRIDO EN ANCHURA
EJEMPLO
A
T
H
B
D
C
R
D
Cola
Se Muestra:
D
B
C
B
C
C
H
H
R
H
R
A
R
A
T
T
A
T
T
RECORRIDO EN PROFUNDIDAD
A
T
H
B
D
C
R
Se Muestra:
Pila
D
D
B
C
C
R
R
H
H
A
T
T
A
B