4.5.8a  Equilibrio de árboles binarios

§1  Sinopsis

En el epígrafe dedicado a la Estructura de la información ( 1.8b) se indicó que el equilibrio del árbol se ve fuertemente afectado por el orden de introducción de los datos, en especial el primero, que constituirá el nodo raíz e influirá en la totalidad del árbol. En consecuencia, este primer elemento afecta grandemente la eficacia de la estructura resultante frente a los mecanismos de datos.

Si el rango de los datos es conocido y se van a introducir gran cantidad de ellos (el árbol será grande), pueden disponerse una medida auxiliar para facilitar el equilibrado; consiste en crear un nodo raíz deliberadamente construido, de forma que corresponda al valor medio de la serie. De esta forma el equilibrio no dependerá de la mejor o peor fortuna en la introducción del primer dato.

§1.1  Como ejemplo modificaremos el de la página anterior, adaptándolo para que solo acepte caracteres alfabéticos (letras mayúsculas y minúsculas):

#include <iostream.h>     //  Creación de árbol binario mejorado

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 del teclado

void main(void) {         // =========================
  char c;
  if ((rz = new(base)) == NULL) {   // crear nodo raíz
      cout << "NO hay memoria suficiente!!" << endl;  return 1;
  }
  rz->let = '\\';         // carácter en el nodo raíz
  rz->izq = rz->der = NULL;
  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
    if (c >= 65 && c <= 91) return c; 
    else if (c >= 97 && c <= 123 ) return c;
    else if ( c == 27 ) return c;
    cout << "\a";
  }
}

int incluir(char letr, struct base* ptr) {    // añadir elemento
  if (letr == ptr->let) return 0;      // El carácter ya existe
  if (letr < ptr->let) {
    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) {
    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

Los cambios son mínimos pero significativos: hemos creado inicialmente el nodo raíz en la propia función main, con el carácter \ (ASCII 92) que está justamente entre las serie de las Mayúsculas y las minúsculas en la ordenación ASCII; por tanto esta parte la sacamos de la función incluir.

Observe la forma de asignación del carácter elegido en el nodo raíz:    rz->let = '\\';

La función acepta es modificada para que solo acepte las letras del abecedario. Si se introduce un carácter incorrecto, se produce una señal acústica (ASCII 7).