Disponible la nueva versión "donationware" 7.3 de OrganiZATOR
Descubre un nuevo concepto en el manejo de la información.
La mejor ayuda para sobrevivir en la moderna jungla de datos la tienes aquí.

Curso C++

[Home]  [Inicio]  [Índice]


4.5.8  Estructuras auto-referenciadas

§1  sinopsis

Las estructuras se utilizan con frecuencia como elementos de estructuras de datos tipo árbol y lista ( 1.8). En estos casos, un conjunto de objetos del mismo tipo, están relacionadas entre sí mediante punteros contenidos en ellos mismos, de forma que basta conocer la raíz del árbol o principio de la lista, para poder acceder a todo el conjunto. En ocasiones, si tales listas son doblemente enlazadas, es posible entrar en cualquier nodo y recorrer la totalidad del conjunto en cualquier sentido. Esta es la razón del apelativo "auto-referenciadas".


§2  Como ejemplo, construiremos un programa que acepte caracteres por el teclado y construya un árbol binario ( 1.8b) cuyos elementos contengan el carácter introducido y estén ordenados según su valor ASCII. En la Fig. 1 se muestra gráficamente el resultado de introducir los caracteres:  b, D, g, A, E y k.

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 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 (caracteres no imprimibles 3.2.3e); 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 ( 1.8b), 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 (NULL 4.2.1). 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" ( 4.9.9) antes de asignarlo a ptr; de lo contrario se obtendría un error.

Nota:  también se podría utilizar el operador new ( 4.9.20), 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 ( 1.3.2).


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 mostraran 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...