Download Un ejemplo: rectas de regresión para una serie de puntos en el plano

Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
Una de las aplicaciones más interesantes y potentes de la memoria dinámica y de los punteros
son, sin duda, las estructuras dinámicas de datos. Las estructuras básicas disponibles en C y C++
(structs y arrays) tienen una importante limitación: no pueden cambiar de tamaño durante la
ejecución. Los arrays están compuestos por un determinado número de elementos, número que
se decide en la fase de diseño, antes de que el programa ejecutable sea creado.
En muchas ocasiones se necesitan estructuras que puedan cambiar de tamaño durante la
ejecución del programa. Por supuesto, podemos crear arrays dinámicos, pero una vez creados,
tu tamaño también será fijo, y para hacer que crezcan o disminuyan de tamaño, deberemos
reconstruirlos desde el principio.
Las estructuras dinámicas nos permiten crear estructuras de datos que se adapten a las
necesidades reales a las que suelen enfrentarse nuestros programas. Pero no sólo eso, como
veremos, también nos permitirán crear estructuras de datos muy flexibles, ya sea en cuanto al
orden, la estructura interna o las relaciones entre los elementos que las componen.
Las estructuras de datos están compuestas de otras pequeñas estructuras a las que llamaremos
nodos o elementos, que agrupan los datos con los que trabajará nuestro programa y además uno
o más punteros autoreferenciales, es decir, punteros a objetos del mismo tipo nodo.
Una estructura básica de un nodo para crear listas de datos seria:
struct nodo {
int dato;
struct nodo *otronodo;
};
El campo "otronodo" puede apuntar a un objeto del tipo nodo. De este modo, cada nodo puede
usarse como un ladrillo para construir listas de datos, y cada uno mantendrá ciertas relaciones
con otros nodos.
Para acceder a un nodo de la estructura sólo necesitaremos un puntero a un nodo.
Durante el presente curso usaremos gráficos para mostrar la estructura de las estructuras de
datos dinámicas. http://www.graphviz.org/
Nodo
Las estructuras dinámicas son una implementación de TDAs o TADs (Tipos Abstractos de
Datos). En estos tipos el interés se centra más en la estructura de los datos que en el tipo
concreto de información que almacenan.
Dependiendo del número de punteros y de las relaciones entre nodos, podemos distinguir
varios tipos de estructuras dinámicas. Enumeraremos ahora sólo de los tipos básicos:

Listas abiertas: cada elemento sólo dispone de un puntero, que apuntará al siguiente
elemento de la lista o valdrá NULL si es el último elemento.
_________________________________________________________________________
Escuela Ingeniería en Computación, Universidad de La Serena.
1
Programación Estructurada( en C)

Estrructuras de Datos
Dr. Eric Jeltsch F.
Pilas: son un tipo especial de lista, conocidas como listas LIFO (Last In, First Out: el
último en entrar es el primero en salir). Los elementos se "amontonan" o apilan, de
modo que sólo el elemento que está encima de la pila puede ser leído, y sólo pueden
añadirse elementos encima de la pila.
Una pila (stack) es una colección ordenada de elementos en la cual se pueden insertar nuevos
elementos por un extremo y se pueden retirar otros por el mismo extremo; ese extremos se
llama ``la parte superior'' de la pila. La dinámica de la pila, es decir, la manera en cómo entran
los datos a la estructura de datos y cómo salen, se denomina fifo, que viene del inglés first in
first out (primero en entrar, primero en salir).
Fig. 1
En la Fig. 1 el elemento F está en la cima, es el más alto de todos los elementos que están en la
pila. El elemento D es el más alto de los elementos A,B,C, pero es menor que los elementos E
y F.
El concepto de pila es muy importante en computación y en especial en teoría de lenguajes de
programación. En lenguajes procedurales como C, la pila es una estructura indispensable,
debido a las llamadas a función. Ya que el flujo de instrucciones va de arriba hacia abajo, y
cuando ocurre una llamada a alguna función, el estado global del sistema se almacena en un
registro y éste en una pila. Así que la pila va a contener todas las llamadas a procedimientos
que se hagan. De manera que, cuando se termina de ejecutar algún procedimiento, se recupera
el registro que está en la cima de la pila. En ese registro están los valores de las variables como
estaban antes de la llamada a la función, o algunas pueden haber cambiado su valor,
dependiendo del ámbito de las variables.
Cada elemento en la pila que es retirado, significa que se ha terminado de ejecutar alguna
función. Cuando se termina de ejecutar el programa, la pila de llamadas a subprogramas debe
haber quedado en 0 también, de otro modo podría causar algún tipo de error o desbordamiento,
también llamado (overflow).
Una pila es un tipo especial de lista abierta en la que sólo se pueden insertar y eliminar nodos
en uno de los extremos de la lista. Estas operaciones se conocen como "push" y "pop",
respectivamente "empujar" y "tirar". Además, las escrituras de datos siempre son inserciones
de nodos, y las lecturas siempre eliminan el nodo leído.
Estas características implican un comportamiento de lista LIFO (Last In First Out), el último en
entrar es el primero en salir.
_________________________________________________________________________
Escuela Ingeniería en Computación, Universidad de La Serena.
2
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
El símil del que deriva el nombre de la estructura es una pila de platos. Sólo es posible añadir
platos en la parte superior de la pila, y sólo pueden tomarse del mismo extremo.
El nodo típico para construir pilas es el mismo que vimos en el capítulo anterior para la
construcción de listas:
struct nodo {
int dato;
struct nodo *siguiente;
};
Los tipos que definiremos normalmente para manejar pilas serán casi los mismos que para
manejar listas, tan sólo cambiaremos algunos nombres:
typedef struct _nodo {
int dato;
struct _nodo *siguiente;
} tipoNodo;
typedef tipoNodo *pNodo;
typedef tipoNodo *Pila;
tipoNodo es el tipo para declarar nodos, evidentemente.
pNodo es el tipo para declarar punteros a un nodo.
Pila es el tipo para declarar pilas.
Teniendo en cuenta que las inserciones y borrados en una pila se hacen siempre en un extremo,
lo que consideramos como el primer elemento de la lista es en realidad el último elemento de la
pila.
Las pilas tienen un conjunto de operaciones muy limitado, sólo permiten las operaciones de
"push" y "pop":


Push: Añadir un elemento al final de la pila.
Pop: Leer y eliminar un elemento del final de la pila.
Las operaciones con pilas son muy simples, no hay casos especiales, salvo que la pila esté
vacía.
Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él,
además el puntero a la pila valdrá NULL:
Push en vacía
El proceso es muy simple, bastará con que:
_________________________________________________________________________
Escuela Ingeniería en Computación, Universidad de La Serena.
3
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
1. nodo->siguiente apunte a NULL.
2. Pila apunte a nodo.
Supongamos que queremos construir una pila para almacenar números enteros. Haremos
pruebas intercalando varios "push" y "pop", y comprobando el resultado.
1. Creamos un nodo para el valor que colocaremos en la pila.
2. Hacemos que nodo->siguiente apunte a Pila.
3. Hacemos que Pila apunte a nodo.
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;
}
1. Hacemos que nodo apunte al primer elemento de la pila, es decir a Pila.
2. Asignamos a Pila la dirección del segundo nodo de la pila: Pila->siguiente.
3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la
operación pop equivale a leer y borrar.
4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.
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;
}
#include <stdlib.h>
_________________________________________________________________________
Escuela Ingeniería en Computación, Universidad de La Serena.
4
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
#include <stdio.h>
typedef struct _nodo {
int valor;
struct _nodo *siguiente;
} tipoNodo;
typedef tipoNodo *pNodo;
typedef tipoNodo *Pila;
/* Funciones con pilas: */
void Push(Pila *l, int v);
int Pop(Pila *l);
int main() {
Pila pila = NULL;
Push(&pila,
Push(&pila,
printf("%d,
Push(&pila,
Push(&pila,
20);
10);
", Pop(&pila));
40);
30);
printf("%d, ", Pop(&pila));
printf("%d, ", Pop(&pila));
Push(&pila, 90);
printf("%d, ", Pop(&pila));
printf("%d\n", Pop(&pila));
getchar();
return 0;
}
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;
}
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;
}
_________________________________________________________________________
Escuela Ingeniería en Computación, Universidad de La Serena.
5
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
#include <stdlib.h>
#include <stdio.h>
typedef struct _nodo {
int valor;
struct _nodo *siguiente;
} tipoNodo;
typedef tipoNodo *pNodo;
typedef tipoNodo *Pila;
/* Funciones con pilas: */
void Push(Pila *l, int v);
int Pop(Pila *l);
int main()
{
Pila pila = NULL;
pNodo p;
Push(&pila,
Push(&pila,
Push(&pila,
Push(&pila,
20);
10);
40);
30);
printf("%d, ",
printf("%d, ",
printf("%d, ",
printf("%d\n",
Pop(&pila));
Pop(&pila));
Pop(&pila));
Pop(&pila));
system("PAUSE");
return 0;
}
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;
}
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;
_________________________________________________________________________
Escuela Ingeniería en Computación, Universidad de La Serena.
6
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
/* Borrar el nodo */
free(nodo);
return v;
}
#include <stdlib.h>
#include <stdio.h>
typedef struct _nodo {
int valor;
struct _nodo *siguiente;
} tipoNodo;
typedef tipoNodo *pNodo;
/* Funciones con colas: */
void Anadir(pNodo *primero, pNodo *ultimo, int v);
int Leer(pNodo *primero, pNodo *ultimo);
int main()
{
pNodo primero = NULL, ultimo = NULL;
Anadir(&primero, &ultimo, 20);
printf("Añadir(20)\n");
Anadir(&primero, &ultimo, 10);
printf("Añadir(10)\n");
printf("Leer: %d\n", Leer(&primero,
Anadir(&primero, &ultimo, 40);
printf("Añadir(40)\n");
Anadir(&primero, &ultimo, 30);
printf("Añadir(30)\n");
printf("Leer: %d\n", Leer(&primero,
printf("Leer: %d\n", Leer(&primero,
Anadir(&primero, &ultimo, 90);
printf("Añadir(90)\n");
printf("Leer: %d\n", Leer(&primero,
printf("Leer: %d\n", Leer(&primero,
&ultimo));
&ultimo));
&ultimo));
&ultimo));
&ultimo));
system("PAUSE");
return 0;
}
void Anadir(pNodo *primero, pNodo *ultimo, int v)
{
pNodo nuevo;
/* Crear un nodo nuevo */
nuevo = (pNodo)malloc(sizeof(tipoNodo));
nuevo->valor = v;
/* Este será el último nodo, no debe tener siguiente */
_________________________________________________________________________
Escuela Ingeniería en Computación, Universidad de La Serena.
7
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
nuevo->siguiente = NULL;
/* Si la cola no estaba vacía, añadimos el nuevo a continuación de ultimo
*/
if(*ultimo) (*ultimo)->siguiente = nuevo;
/* Ahora, el último elemento de la cola es el nuevo nodo */
*ultimo = nuevo;
/* Si primero es NULL, la cola estaba vacía, ahora primero apuntará
también al nuevo nodo */
if(!*primero) *primero = nuevo;
}
int Leer(pNodo *primero, pNodo *ultimo)
{
pNodo nodo; /* variable auxiliar para manipular nodo */
int v;
/* variable auxiliar para retorno */
/* Nodo apunta al primer elemento de la pila */
nodo = *primero;
if(!nodo) return 0; /* Si no hay nodos en la pila retornamos 0 */
/* Asignamos a primero la dirección del segundo nodo */
*primero = nodo->siguiente;
/* Guardamos el valor de retorno */
v = nodo->valor;
/* Borrar el nodo */
free(nodo);
/* Si la cola quedó vacía, ultimo debe ser NULL también*/
if(!*primero) *ultimo = NULL;
return v;
}
Aplicación de Pilas:
Supongamos ahora la expresión ((5+6)*4)/(17+9), una de las condiciones para que una
expresión aritmética sea correcta, es que tenga sus paréntesis balanceados, así que deseamos
saber si el número de paréntesis que abres es el mismo número de paréntesis que cierran.
Para resolver este problema se usa el concepto de pila. La idea es simple. Vamos a leer cada
elemento de la expresión, si se trata de un paréntesis que abre, entonces lo insertaremos en una
pila; si se trata de un paréntesis que cierra, entonces sacamos un elemento de la pila. Al
terminar de leer la expresión revisaremos si la pila está vacía, en cuyo caso habremos
concluido que el número de paréntesis que abre es el mismo que el número de paréntesis que
cierra y la expresión tiene paréntesis balanceados.
Veamos cómo funciona:
_________________________________________________________________________
Escuela Ingeniería en Computación, Universidad de La Serena.
8
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
`(' :
push(S,`(')
`(' :
push(S,`(')
`5' :
nada que hacer
`+' :
nada que hacer
`6' :
nada que hacer
`)' :
v=pop(S)
`*' :
nada que hacer
`4' :
nada que hacer
`)' :
v=pop(S)
`/' :
nada que hacer
`(' :
push(S,`(')
`17':
nada que hacer
`+' :
nada que hacer
`9' :
nada que hacer
`)' :
v=pop(S)
Colas: otro tipo de listas, conocidas como listas FIFO (First In, First Out: El primero en entrar
es el primero en salir). Los elementos se almacenan en fila, pero sólo pueden añadirse por un
extremo y leerse por el otro. Las colas son una estructura de datos similar a las pilas.
Recordemos que las pilas funcionan en un depósito en donde se insertan y se retiran elementos
por el mismo extremo. En las colas sucede algo diferente, se insertan elementos por un extremo
_________________________________________________________________________
Escuela Ingeniería en Computación, Universidad de La Serena.
9
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
y se retiran elementos por el otro extremo. De hecho a este tipo de dispositivos se les conoce
como dispositivos ``fifo'' (first in, first out) porque funcionan como una tubería, lo que entra
primero por un extremo, sale primero por el otro extremo. En una cola hay dos extremos, uno
es llamado la parte delantera y el otro extremo se llama la parte trasera de la cola. En una
cola, los elementos se retiran por la parte delantera y se agregan por la parte trasera.





Listas circulares: o listas cerradas, son parecidas a las listas abiertas, pero el último
elemento apunta al primero. De hecho, en las listas circulares no puede hablarse de
"primero" ni de "último". Cualquier nodo puede ser el nodo de entrada y salida.
Listas doblemente enlazadas: cada elemento dispone de dos punteros, uno a punta al
siguiente elemento y el otro al elemento anterior. Al contrario que las listas abiertas
anteriores, estas listas pueden recorrerse en los dos sentidos.
Arboles: cada elemento dispone de dos o más punteros, pero las referencias nunca son a
elementos anteriores, de modo que la estructura se ramifica y crece igual que un árbol.
Arboles binarios: son árboles donde cada nodo sólo puede apuntar a dos nodos.
Arboles binarios de búsqueda (ABB): son árboles binarios ordenados. Desde cada nodo
todos los nodos de una rama serán mayores, según la norma que se haya seguido para
ordenar el árbol, y los de la otra rama serán menores.
/* Arbol Binario de Búsqueda en C
*/
_________________________________________________________________________ 10
Escuela Ingeniería en Computación, Universidad de La Serena.
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
#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);
_________________________________________________________________________ 11
Escuela Ingeniería en Computación, Universidad de La Serena.
Programación Estructurada( en C)
Insertar(&ArbolInt,
Insertar(&ArbolInt,
Insertar(&ArbolInt,
Insertar(&ArbolInt,
Insertar(&ArbolInt,
Insertar(&ArbolInt,
Insertar(&ArbolInt,
Insertar(&ArbolInt,
Insertar(&ArbolInt,
Insertar(&ArbolInt,
Estrructuras de Datos
Dr. Eric Jeltsch F.
11);
14);
13);
2);
1);
15);
10);
17);
18);
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;
}
_________________________________________________________________________ 12
Escuela Ingeniería en Computación, Universidad de La Serena.
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
/* 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)) {
_________________________________________________________________________ 13
Escuela Ingeniería en Computación, Universidad de La Serena.
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
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*))
{
_________________________________________________________________________ 14
Escuela Ingeniería en Computación, Universidad de La Serena.
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
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 */
_________________________________________________________________________ 15
Escuela Ingeniería en Computación, Universidad de La Serena.
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
/* 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);
}
_________________________________________________________________________ 16
Escuela Ingeniería en Computación, Universidad de La Serena.
Programación Estructurada( en C)

Estrructuras de Datos
Dr. Eric Jeltsch F.
Arboles AVL: son también árboles de búsqueda, pero su estructura está más optimizada
para reducir los tiempos de búsqueda.
#include <stdlib.h>
#include <stdio.h>
#define TRUE 1
#define FALSE 0
enum {IZQUIERDO, DERECHO};
/* Estructuras y tipos */
typedef struct _nodo {
int dato;
int FE;
struct _nodo *derecho;
struct _nodo *izquierdo;
struct _nodo *padre;
} tipoNodo;
typedef tipoNodo *pNodo;
typedef tipoNodo *Arbol;
/* Funciones con árboles: */
/* Insertar en árbol ordenado: */
void Insertar(Arbol *a, int dat);
_________________________________________________________________________ 17
Escuela Ingeniería en Computación, Universidad de La Serena.
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
/* 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 de equilibrado:
void Equilibrar(Arbol *raiz, pNodo nodo, int, int);
void RSI(Arbol *raiz, pNodo nodo);
void RSD(Arbol *raiz, pNodo nodo);
void RDI(Arbol *raiz, pNodo nodo);
void RDD(Arbol *raiz, pNodo nodo);
/* 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: */
_________________________________________________________________________ 18
Escuela Ingeniería en Computación, Universidad de La Serena.
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
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)
_________________________________________________________________________ 19
Escuela Ingeniería en Computación, Universidad de La Serena.
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
{
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;
(*a)->padre = NULL;
(*a)->FE = 0;
}
/* 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;
actual->padre = padre;
actual->FE = 0;
Equilibrar(a, padre, IZQUIERDO, TRUE);
}
/* 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;
actual->padre = padre;
actual->FE = 0;
Equilibrar(a, padre, DERECHO, TRUE);
}
}
/* Equilibrar árbol AVL partiendo del nodo nuevo */
void Equilibrar(Arbol *a, pNodo nodo, int rama, int nuevo)
{
int salir = FALSE;
/* Recorrer camino inverso actualizando valores de FE: */
while(nodo && !salir) {
if(nuevo)
if(rama == IZQUIERDO) nodo->FE--; /* Depende de si añadimos ... */
else
nodo->FE++;
else
if(rama == IZQUIERDO) nodo->FE++; /* ... o borramos */
else
nodo->FE--;
if(nodo->FE == 0) salir = TRUE; /* La altura de las rama que
empieza en nodo no ha variado,
salir de Equilibrar */
else if(nodo->FE == -2) { /* Rotar a derechas y salir: */
_________________________________________________________________________ 20
Escuela Ingeniería en Computación, Universidad de La Serena.
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
if(nodo->izquierdo->FE == 1) RDD(a, nodo); /* Rotación doble */
else RSD(a, nodo);
/* Rotación simple */
salir = TRUE;
}
else if(nodo->FE == 2) { /* Rotar a izquierdas y salir: */
if(nodo->derecho->FE == -1) RDI(a, nodo); /* Rotación doble */
else RSI(a, nodo);
/* Rotación simple */
salir = TRUE;
}
if(nodo->padre)
if(nodo->padre->derecho == nodo) rama = DERECHO; else rama
IZQUIERDO;
nodo = nodo->padre; /* Calcular FE, siguiente nodo del camino. */
}
}
=
/* Rotación doble a derechas */
void RDD(Arbol *raiz, Arbol nodo)
{
pNodo Padre = nodo->padre;
pNodo P = nodo;
pNodo Q = P->izquierdo;
pNodo R = Q->derecho;
pNodo B = R->izquierdo;
pNodo C = R->derecho;
if(Padre)
if(Padre->derecho == nodo) Padre->derecho = R;
else Padre->izquierdo = R;
else *raiz = R;
/* Reconstruir árbol: */
Q->derecho = B;
P->izquierdo = C;
R->izquierdo = Q;
R->derecho = P;
/* Reasignar padres: */
R->padre = Padre;
P->padre = Q->padre = R;
if(B) B->padre = Q;
if(C) C->padre = P;
/* Ajustar valores de FE: */
switch(R->FE) {
case -1: Q->FE = 0; P->FE = 1; break;
case 0: Q->FE = 0; P->FE = 0; break;
case 1: Q->FE = -1; P->FE = 0; break;
}
R->FE = 0;
}
/* Rotación doble a izquierdas */
void RDI(Arbol *a, pNodo nodo)
{
pNodo Padre = nodo->padre;
pNodo P = nodo;
pNodo Q = P->derecho;
pNodo R = Q->izquierdo;
pNodo B = R->izquierdo;
pNodo C = R->derecho;
if(Padre)
_________________________________________________________________________ 21
Escuela Ingeniería en Computación, Universidad de La Serena.
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
if(Padre->derecho == nodo) Padre->derecho = R;
else Padre->izquierdo = R;
else *a = R;
/* Reconstruir árbol: */
P->derecho = B;
Q->izquierdo = C;
R->izquierdo = P;
R->derecho = Q;
/* Reasignar padres: */
R->padre = Padre;
P->padre = Q->padre = R;
if(B) B->padre = P;
if(C) C->padre = Q;
/* Ajustar valores de FE: */
switch(R->FE) {
case -1: P->FE = 0; Q->FE = 1; break;
case 0: P->FE = 0; Q->FE = 0; break;
case 1: P->FE = -1; Q->FE = 0; break;
}
R->FE = 0;
}
/* Rotación simple a derechas */
void RSD(Arbol *a, pNodo nodo)
{
pNodo Padre = nodo->padre;
pNodo P = nodo;
pNodo Q = P->izquierdo;
pNodo B = Q->derecho;
if(Padre)
if(Padre->derecho == P) Padre->derecho = Q;
else Padre->izquierdo = Q;
else *a = Q;
/* Reconstruir árbol: */
P->izquierdo = B;
Q->derecho = P;
/* Reasignar padres: */
P->padre = Q;
if(B) B->padre = P;
Q->padre = Padre;
/* Ajustar valores de FE: */
P->FE = 0;
Q->FE = 0;
}
/* Rotación simple a izquierdas */
void RSI(Arbol *a, pNodo nodo)
{
pNodo Padre = nodo->padre;
pNodo P = nodo;
pNodo Q = P->derecho;
pNodo B = Q->izquierdo;
if(Padre)
if(Padre->derecho == P) Padre->derecho = Q;
else Padre->izquierdo = Q;
_________________________________________________________________________ 22
Escuela Ingeniería en Computación, Universidad de La Serena.
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
else *a = Q;
/* Reconstruir árbol: */
P->derecho = B;
Q->izquierdo = P;
/* Reasignar padres: */
P->padre = Q;
if(B) B->padre = P;
Q->padre = Padre;
/* Ajustar valores de FE: */
P->FE = 0;
Q->FE = 0;
}
/* 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;
/* El nodo padre del actual puede ser ahora un nodo hoja, por lo
tanto su FE es cero, pero debemos seguir el camino a partir
de
su padre, si existe. */
if((padre->derecho == actual && padre->FE == 1) ||
(padre->izquierdo == actual && padre->FE == -1)) {
padre->FE = 0;
actual = padre;
padre = actual->padre;
}
if(padre)
if(padre->derecho == actual) Equilibrar(a, padre,
DERECHO,
FALSE);
else
Equilibrar(a, padre, IZQUIERDO,
FALSE);
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 */
_________________________________________________________________________ 23
Escuela Ingeniería en Computación, Universidad de La Serena.
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
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;
_________________________________________________________________________ 24
Escuela Ingeniería en Computación, Universidad de La Serena.
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
/* 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)
{
_________________________________________________________________________ 25
Escuela Ingeniería en Computación, Universidad de La Serena.
Programación Estructurada( en C)
Estrructuras de Datos
Dr. Eric Jeltsch F.
/* 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);
}


Arboles B: son estructuras más complejas, aunque también se trata de árboles de
búsqueda, están mucho más optimizados que los anteriores.
Tablas HASH: son estructuras auxiliares para ordenar listas.
_________________________________________________________________________ 26
Escuela Ingeniería en Computación, Universidad de La Serena.
Programación Estructurada( en C)


Estrructuras de Datos
Dr. Eric Jeltsch F.
Grafos: es el siguiente nivel de complejidad, podemos considerar estas estructuras
como árboles no jerarquizados.
Diccionarios.
Al final del curso también veremos estructuras dinámicas en las que existen nodos de distintos
tipos, en realidad no es obligatorio que las estructuras dinámicas estén compuestas por un
único tipo de nodo, la flexibilidad y los tipos de estructuras sólo están limitados por tu
imaginación como programador.
_________________________________________________________________________ 27
Escuela Ingeniería en Computación, Universidad de La Serena.