Buscar un String con un Árbol Binario de Búsqueda

publicado por: Anonymous

Tengo que realizar una búsqueda para poder listar nombres de doctores, lo estoy haciendo con un ABB en Java pero lo que no me queda claro es como poder retornar el String, a continuación pongo el código del buscar:

Tanto raíz como dato son AnyType creo que un problema que estoy teniendo puede ser el de la comparación en el if ya que no puedo comparar un String como si fuera un int, no sé si me explico.

public NodoArbol buscarDoctor(String d)
{
    NodoArbol aux = raiz;
    while(aux.dato != d)
    {
        if(d < aux.dato)
        {
            aux = aux.primerHijo;
        }
        else
        {
            aux = aux.siguienteHermano;
        }
        if(aux == null)
        {
            return null; //No lo encontró.
        }
    }
    return aux;        
}

Ojalá alguien me pueda ayudar, gracias de antemano.

solución

El valor en cada nodo de un árbol de búsqueda binario debe ser comparable. Esto es, que en Java cada valor debería ser una instancia de una clase que implemente la interfaz java.lang.Comparable. Puesto que estás usando instancias de la java.lang.String, esta ya la implementa.

El algoritmo de búsqueda típico en esta estructura de datos es el siguiente:

[…] consiste en acceder a la raíz del árbol, si el elemento a localizar coincide con éste la búsqueda ha concluido con éxito, si el elemento es menor se busca en el subárbol izquierdo y si es mayor en el derecho. Si se alcanza un nodo hoja y el elemento no ha sido encontrado se supone que no existe en el árbol.

Esto puede expresarse en código como sigue (utilizando los nombres de variables adecuados):

public String buscarDoctor(String d) {
    return buscarDoctor(raiz, d);
}

private String buscarDoctor(NodoArbol aux, String str) {
    if (aux == null) {
        return null;
    }
    int cmp = str.compareTo(aux.dato);
    if (cmp < 0) {
        return get(aux.izquierda, str);
    } else if (cmp > 0) {
        return get(aux.derecha, str);
    } else {
        return aux.dato;
    }
}
Respondido por: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *