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