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.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;
}