Análisis
y Diseño de Algoritmos
Prof:
Ing. Victor Garro
Asistente:
Marco Elizondo Vargas
Recursión
estructuras
auto referenciadas
Las estructuras se utilizan con frecuencia como elementos de estructuras
de datos tipo árbol y lista. En estos casos, un
conjunto de estructuras del mismo tipo, están relacionadas entre sí mediante
punteros, de forma que basta conocer la raíz del árbol o principio de la lista,
para poder acceder a todo el conjunto; esta es la razón del apelativo
"auto referenciadas".
El programa acepta caracteres indefinidamente (mientras
exista memoria suficiente o se pulse ESC). Después de la introducción de
cada nuevo elemento, se muestra ordenadamente la totalidad del árbol.
#include
<iostream.h> //
Ejemplo de creación de árbol binario
struct base
{
// declara tipo de estructura a utilizar
char
let;
// para almacenar carácter
struct base*
izq; // puntero
izquierdo
struct base*
der; // puntero
derecho
} *rz,
*aptr;
// rz puntero al nodo raíz; aptr puntero auxiliar
int incluir(char letra, struct base* puntero);
void inorden (struct base* puntero);
char acepta (void);
// aceptar datos por teclado
void main(void)
{ //
=========================
char c;
while ( (c = acepta()) != 27) { // Bucle
principal
if (incluir(c, rz)) break;
inorden(rz);
}
}
char acepta (void) { //
Introducir datos por teclado
char c;
cout << "\n Pulse un carácter + [CR] ";
while (1) {
c = getchar();
if (c == 10) continue; // 10 == New Line
return c;
}
}
int incluir(char letr, struct base* ptr)
{ // añadir elemento
if (rz == NULL)
{ // 1o. solo la
primera vez!!!
rz = (struct base*) malloc(sizeof(base));
if (rz == NULL) {
cout << "NO hay memoria
suficiente!!" << endl; return 1;
}
rz->let = letr;
rz->izq = rz->der = NULL;
return 0;
}
if (letr == ptr->let) return 0; // 2o.
El carácter ya existe
if (letr < ptr->let) { // 3o.
if (ptr->izq == NULL)
{ // enlace libre: incluir
aptr = (struct base*) malloc(sizeof(base));
if (aptr == NULL) {
cout << "NO queda
suficiente memoria" << endl; return 1;
}
aptr->let = letr;
aptr->izq = aptr->der = NULL;
ptr->izq = aptr;
return 0;
}
if (incluir(letr,
ptr->izq)) // ocupado: seguir buscando
return
1;
// falla la inserción
}
if (letr > ptr->let) { // 4o.
if (ptr->der == NULL)
{ // enlace libre: incluir
aptr = (struct base*) malloc(sizeof(base));
if (aptr == NULL) {
cout << "NO queda
suficiente memoria" << endl; return 1;
}
aptr->let = letr;
aptr->izq = aptr->der = NULL;
ptr->der = aptr;
return 0;
}
if (incluir(letr,
ptr->der)) // ocupado: seguir buscando
return
1;
// falla la inserción
}
return 0;
}
void inorden (struct base* ptr) { // Recorrer
árbol
if (ptr == NULL) return;
inorden(ptr->izq);
cout << " - " << ptr->let;
inorden(ptr->der);
}
Comentario:
La primera parte declara la estructura, base, que será
utilizada en cada nodo; contiene un carácter para alojar el introducido por
teclado y los dos punteros que necesitan los elementos de los árboles
binarios. Además se definen dos punteros-a-base; uno de ellos, rz,
apuntará desde el primer momento al nodo raíz; el otro, aptr, es un puntero
auxiliar que se necesita en la función incluir.
Además de main, el programa solo tiene tres sencillas
funciones: incluir, que incluye cada nuevo elemento en el árbol con el carácter
pulsado; inorden, que recorre el árbol ordenadamente mostrando en pantalla los
caracteres, y acepta, que simplemente captura los datos del teclado.
La función main consiste en un simple bucle que acepta
indefinidamente caracteres del teclado (mientras no se pulse la tecla Escape);
inserta en el árbol el carácter introducido, y finalmente muestra la totalidad
del árbol hasta el momento. El proceso se termina si por alguna razón
(por ejemplo, falta de memoria) falla el proceso de insertar el carácter, en
cuyo caso la función incluir devuelve 1.
La función acepta no merece ningún comentario; aunque quizás
se podría haber afinado un poco más para no aceptar secuencias de escape,
simplemente letras mayúsculas, o minúsculas, dígitos, etc. Puesto que se
ha utilizado la función getchar, es necesario pulsar también Intro con
cada inserción.
Puede sorprender la extremada simplicidad de la función inorden; esta función
recursiva recorre la totalidad del árbol mostrando de forma ordenada el
carácter contenido en cada elemento. Es de destacar que en realidad la función:
void recorrido (struct base* ptr) {
if (ptr == NULL) return;
recorrido(ptr->izq);
recorrido(ptr->der);
}
recorrería la totalidad del árbol pasando por todos los
nodos. Para recorrerlo en las formas preorden y postorden,
habría que sustituir inorden por las funciones que se indican a
continuación. Observe que la diferencia es pequeñísima entre las tres,
simplemente la posición del la sentencia que muestra el carácter en pantalla.
void preorden (struct base* ptr) { //
recorrido preorden
if (ptr == NULL) return;
cout << " - " << ptr->let;
preorden(ptr->izq);
preorden(ptr->der);
}
void postorden (struct base* ptr) { // recorrido postorden
if (ptr == NULL) return;
postorden(ptr->izq);
postorden(ptr->der);
cout << " - " << ptr->let;
}
La función incluir, que crea cada nuevo nodo del árbol con el carácter
introducido, es recursiva (como muchas de las que tratan con árboles) y muy
sencilla, pero merece algún comentario:
El cuerpo del primer if, solo se ejecuta la primera
vez, cuando incluir es invocada desde main después de introducido el
primer carácter, y el puntero rz tiene todavía su valor de inicialización. Este
valor previo para rz y aptr es proporcionado directamente por el compilador en
el momento de la declaración de estas variables globales. Este bloque se
encarga de la creación del nodo raíz (en adelante, durante todo el programa rz
señala a dicho nodo). A este respecto, obsérvese que incluir siempre es
invocada desde main con el valor rz como argumento, es decir: el proceso de
inclusión se inicia siempre empezando por la raíz del árbol.
En este bloque hay que resaltar las sentencias encargadas de asignar memoria
para el nuevo elemento; estas sentencias se repiten cada vez que se crea un
elemento nuevo (en los if 3º y 4º), y contienen un mecanismo de control
que avisa si la memoria disponible se ha agotado:
ptr
= (struct base*) malloc(sizeof(base));
if (ptr == NULL) {
cout << "NO hay memoria suficiente!!" <<
endl; return 1;
}
El manual de la Librería Estándar nos señala que a la función
malloc hay que pasarle un entero con el tamaño del bloque de memoria que
queremos reservar -en nuestro caso sizeof(base)-, y que devuelve un
puntero a la zona de memoria asignada o un NULL si falla en el intento (cosa
que aprovechamos). Observe que al valor malloc(sizeof(base)) le aplicamos
un "casting" antes de asignarlo a ptr; de lo contrario se obtendría
un error.
Nota:
También se podría utilizar el operador new, más moderno que malloc;
las sentencias anteriores serían entonces:
if ((ptr = new(base)) == NULL) {
cout << "NO hay memoria suficiente!!"
<< endl; return 1;
}
Cualquiera que fuese la función
utilizada para crear los nuevos elementos, hay que considerar que tanto new
como malloc reservan espacio del montón. En un programa
real en el que se construyeran árboles como el presente, a fin de evitar
pérdidas de memoria cuando ya no fuesen necesarios, deberían tenerse en cuenta
las observaciones respecto a la persistencia de este tipo de objetos.
El segundo if simplemente no hace nada, pero acepta la entrada como
válida. Ocurre cuando el carácter ya existe previamente en el árbol (se ha
repetido). El cuerpo de este bloque podría modificarse fácilmente; por
ejemplo para incluir un contador que señalara cuantas repeticiones se han
pulsado de cada tecla. Para esto, en el diseño de la estructura base
incluiríamos un campo numérico que inicializaríamos a cero e incrementaríamos
con cada repetición.
Sugerencia:
En este caso también podríamos definir sendas variables globales: total y
repet, que mostrara el total de elementos en el árbol y el total de
repeticiones. Sus valores se actualizarían fácilmente en la función
inorden o después de cada entrada en la propia función incluir.
El tercero y el cuarto if son los encargados de la creación de los
nuevos nodos después de creado el nodo raíz. Cuando llega a este punto,
el nodo raíz ya existe, el árbol es ya más o menos grande y la invocación se ha
realizado desde main o se trata de una de las múltiples recursiones posibles.
Mediante estas recursiones, incluir trepa (aquí deberíamos decir desciende) por
el árbol siguiendo los enlaces izquierdos si el carácter a incluir es menor que
el de los nodos que se va encontrando y a la inversa si es mayor. Cuando
encuentra un nodo terminal adecuado, con el enlace izquierdo o derecho libre
(respectivamente), solicita memoria; rellena los datos del nuevo nodo y lo
cuelga del nodo terminal encontrado, cuyo enlace izquierdo o derecho se
actualiza.
El nodo recién incluido es ahora terminal; sus dos enlaces
están a cero y contiene el nuevo carácter. En este momento la función
termina devolviendo el valor 0 (finalización con éxito), y el control vuelve a
main, donde seguirá el bucle mediante la invocación de inorden...