Análisis
y Diseño de Algoritmos
Prof:
Ing. Victor Garro
Asistente:
Marco Elizondo Vargas
Recursión
Buscar Elemento
Hemos señalado que se dispone de
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; nosotros
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;
}
Nota: 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.
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 ?
Como complemento del ejercicio
anterior, presentamos una variante utilizando el manejador de excepciones C++ 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;