4.5.8b Buscar elementos en árboles binarios
§1 Sinopsis
Hemos señalado que existen algoritmos muy eficientes para recuperar información de los árboles binarios ordenados. El algoritmo para buscar un valor puede ser una modificación de la función incluir del ejemplo de la página anterior. Allí la función no hace nada si el carácter coincide con uno ya existente; aquí aprovecharemos precisamente esta característica para que nos devuelva un puntero al elemento, o un puntero nulo (NULL) si el carácter no existe en el árbol. La función a la que denominaremos busca, tiene el aspecto siguiente ( key es la clave a buscar):
struct base* busca(char key, struct base* ptr)
{ // buscar key
if (key == ptr->let) return ptr; //
Ok. encuentro!
if (key < ptr->let) { // debe estar en
la rama izquierda
if (ptr->izq == NULL) return NULL; // no existe
busca(key, ptr->izq); // enlace
ocupado: seguir buscando
}
if (key > ptr->let) { // debe estar en
la rama derecha
if (ptr->der == NULL) return NULL; // no existe
busca(key, ptr->der); // enlace
ocupado: seguir buscando
}
return NULL;
}
Por las razones expuestas al hablar de la recursión (
4.4.6c), esta función no puede ser directamente utilizada en su forma actual, por lo que modificaremos
ligeramente su diseño antes de su utilización en el siguiente ejemplo.
§2 Ejemplo
Para comprobar la veracidad del código, modificamos el programa del árbol binario mejorado de la página anterior, de forma que en cualquier momento, introduciendo el carácter "?", el programa realiza la búsqueda del siguiente carácter que se introduzca por teclado en vez de incluirlo en el árbol, que es el comportamiento normal.
#include <iostream.h> // Árbol binario con búsqueda
struct base { // Estructura a utilizar
char let;
struct base* izq;
struct base* der;
} *rz, *aptr;
char previo, ant; // globales auxiliares
int incluir(char letra, struct base* puntero);
void inorden (struct base* puntero);
char acepta (void); // aceptar datos del teclado
void busca(char key, struct base* puntero); // buscar
void nodo(struct base* puntero); // mostrar resultado de busqueda
void main(void) { // ==========================
char c;
if ((rz = new(base)) == NULL) { // crear nodo raíz
cout << "NO queda memoria" << endl; return 1;
}
rz->let = '\\';
// carácter en el nodo raíz
rz->izq = rz->der = NULL;
while ( (c = acepta()) != 27) { // Bucle principal
if (c == '?') { previo = c; continue; }
else if (previo == '?') {
previo = c;
aptr = NULL;
busca(c, rz); // buscar caracter en el arbol
nodo(aptr); // mostrar resultado de la busqueda
continue;
}
else if (incluir(c, rz)) break;
inorden(rz);
}
}
char acepta (void) { // Introducir datos por teclado
char c;
cout << "\n Pulse un caracter + [CR] ";
while (1) {
c = getchar();
if (c == 10) continue; // 10 == New Line
if (c >= 65 && c <= 91) return c;
if (c >= 97 && c <= 123 ) return c;
if (c == 27 || c == '?') 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 << "Memoria agotada" << endl; return 1; }
aptr->let = letr;
aptr->izq = aptr->der = NULL;
ptr->izq = aptr;
return 0;
}
if (incluir(letr, ptr->izq)) 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 << "Memoria agotada" << endl; return 1; }
aptr->let = letr;
aptr->izq = aptr->der = NULL;
ptr->der = aptr;
return 0;
}
if (incluir(letr, ptr->der)) 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);
}
void busca(char key, struct base* ptr) { // buscar key
if (key == ptr->let) { aptr = ptr; return; }
ant = ptr->let;
if (key < ptr->let) { // debe
estar en rama izquierda
if (ptr->izq == NULL) return; // no existe
busca(key, ptr->izq); // seguir búsqueda
}
if (key > ptr->let) { //
debe estar en rama derecha
if (ptr->der == NULL) return; // no existe
busca(key, ptr->der); // seguir búsqueda
}
return;
}
void nodo(struct base* ptr) { // mostrar resultado
if (ptr == NULL) { cout << "No encontrado\a" << endl; return; }
char izq = '#', der = '#', key = ptr->let;
if (ptr->izq != NULL) izq = ptr->izq->let; // letra nodo izq.
if (ptr->der != NULL) der = ptr->der->let; // letra nodo der.
cout << "\n " << ant << endl;
cout << " |" << endl;
cout << " " << key << endl;
cout << "/ \\" << endl;
cout << izq << " " << der << endl;
}
Comentario
Introducimos dos nuevas variables globales: previo y ant, que alojarán respectivamente el último carácter pulsado, y el carácter del nodo anterior (raíz) del que se busca.
Igualmente introducimos dos nuevas funciones: busca y nodo. La primera ya se ha comentado, se utiliza para buscar un carácter. La segunda, a la que se pasa un puntero al nodo encontrado, muestra el detalle de los enlaces o anuncia el fallo en la búsqueda (el puntero es nulo).
La función acepta ha sufrido un ligerísimo cambio para permitir introducir el carácter "?"
§3 Ejemplo
Como complemento del ejercicio anterior, presentamos una variante utilizando el manejador de excepciones C++
( 1.6) para realizar un retorno desde
la función busca hasta main cuando ocurre un encuentro. Se lanza entonces una excepción que es precisamente el
puntero al nodo encontrado. Esta excepción es capturada y entonces se muestra el detalle del nodo. Como la función nodo
solo es llamada en caso de búsqueda con éxito, es necesario modificarla ligeramente y sacar fuera de ella el mensaje de búsqueda
fallida. Como puede verse, esta adaptación del programa solo exige muy pequeñas modificaciones.
#include <iostream.h> // Árbol binario con búsqueda (II)
struct base { // Estructura a utilizar
char let;
struct base* izq;
struct base* der;
} *rz, *aptr;
char previo, ant;
// globales auxiliares
int incluir(char letra, struct base* puntero);
void inorden (struct base* puntero);
char acepta (void);
// aceptar datos del teclado
void busca(char key, struct base* puntero); // buscar
void nodo(struct base* puntero); // mostrar resultado de busqueda
int main(void) { // ==========================
char c;
if ((rz = new(base)) == NULL) { // crear nodo raíz
cout << "NO queda memoria" << endl; return 1;
}
rz->let = '\\'; // carácter en el nodo raíz
rz->izq = rz->der = NULL;
while ( (c = acepta()) != 27) { // Bucle principal
if (c == '?') { previo = c; continue; }
else if (previo == '?') {
previo = c;
try { busca(c, rz); } // bloque try (buscar)
catch (struct base* ptr) { nodo(ptr); continue; }
cout << "No encontrado\a" << endl;
continue;
}
else if (incluir(c, rz)) break;
inorden(rz);
}
}
char acepta (void) { // Introducir datos por teclado
char c;
cout << "\n Pulse un caracter + [CR] ";
while (1) {
c = getchar();
if (c == 10) continue; // 10 == New Line
if (c >= 65 && c <= 91) return c;
if (c >= 97 && c <= 123 ) return c;
if (c == 27 || c == '?') 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 memoria" << endl; return 1; }
aptr->let = letr;
aptr->izq = aptr->der = NULL;
ptr->izq = aptr;
return 0;
}
if (incluir(letr, ptr->izq)) 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 memoria" << endl; return 1; }
aptr->let = letr;
aptr->izq = aptr->der = NULL;
ptr->der = aptr;
return 0;
}
if (incluir(letr, ptr->der)) 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);
}
void busca(char key, struct base* ptr) { // buscar key
if (key == ptr->let) { throw(ptr); } // lanzar excepcion
ant = ptr->let;
if (key < ptr->let) { // debe estar en rama izquierda
if (ptr->izq == NULL) return; // no existe
busca(key, ptr->izq); // seguir búsqueda
}
if (key > ptr->let) { // debe estar en rama derecha
if (ptr->der == NULL) return; // no existe
busca(key, ptr->der); // seguir búsqueda
}
return;
}
void nodo(struct base* ptr) { // mostrar resultado
char izq = '#', der = '#', key = ptr->let;
if (ptr->izq != NULL) izq = ptr->izq->let; // letra nodo izq.
if (ptr->der != NULL) der = ptr->der->let; // letra nodo der.
cout << "\n " << ant << endl;
cout << " |" << endl;
cout << " " << key << endl;
cout << "/ \\" << endl;
cout << izq << " " << der << endl;
}