buscar un árbol de búsqueda binaria

Question

Estoy tratando de encontrar un nombre dentro de una clave. Creo que se está recuperando bien. Sin embargo, su entrada hasta que no se encontró. tal vez mi código está en algún lugar equivocado?

if (database.retrieve(name, aData))  // both contain the match

en main()

static void retrieveItem(char *name, data& aData)
{
cout << ">>> retrieve " << name << endl << endl;
if (database.retrieve(name, aData))            // name and aData both contain the match
    cout << aData << endl;
else
    cout << "not found\n";
cout << endl;
     }

     static void removeItem(char *name)
    {
cout << ">>> remove " << name << endl << endl;
if (database.remove(name))
    cout << name << " removed\n";
else
    cout << name << " not found\n";
cout << endl;
    }

   int main()
   {
   #ifdef _WIN32
// request memory leak report in Output Window after main returns
_CrtSetDbgFlag ( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF );
   #endif

data    aData;


     << "Database Of Great Computer Scientists\n\n";

database.insert(data("Ralston, Anthony"));
database.insert(data("Liang, Li"));
database.insert(data("Jones, Doug"));
database.insert(data("Goble, Colin"));
database.insert(data("Knuth, Donald"));
database.insert(data("Kay, Alan"));
database.insert(data("Von Neumann, John"));
database.insert(data("Trigoboff, Michael"));
database.insert(data("Turing, Alan"));
displayDatabase(true);
retrieveItem("Trigoboff, Michael", aData);
retrieveItem("Kaye, Danny", aData);

removeItem("Ralston, Anthony");
displayDatabase(true);

Función de recuperar ...

bool BST::retrieve(const char *key, data &aData, int parent) const
 {

for(int index=0; index < maxsize+1; index++)
{

    if (!items[index].empty) 
    {


        if ( items[index].instanceData == key )
        {
            aData.setName(key);
            return true;                   // doesn't return right away
        }


    }

}


 }

y definido en data.cpp

bool operator== (const data& d1, const data& d2)
{

return strcmp(d1.getName(), d2.getName()) == 0;

}

por lo que este trozo de código dentro de main () es donde dice que no se encuentra cuando yo creo que debería estar funcionando correctamente. el nombre y aDatos contienen el nombre correcto que se encontró ..

static void retrieveItem(char *name, data& aData)
{
cout << ">>> retrieve " << name << endl << endl;
if (database.retrieve(name, aData))            // name and aData both contain the match
    cout << aData << endl;
else
    cout << "not found\n";
cout << endl;
     }

Answer 1

Usted debe estar utilizando el BST para navegar a través del árbol - no recorrer distintos elemento de la matriz, como otros han dicho. Pruebe algo como:

bool retrieve(key, aData)
  retrieve(key, aData, parent)
  if (key == aData)
    return true
  else
    return false

bool retrieve(key, aData, parent)
  if (key == items[parent].name)
    aData.setName(key)
  else if (key < items[parent].name)
    retrieve(key, aData, 2*parent+1)
  else
    retrieve(key, aData, 2*parent+2)

Esto debería funcionar bien! :)

Answer 2

No soy un experto en C ++, pero en realidad se está evaluando su operador ==? Se supone que debe tomar dos referencias de datos const, pero parece estar comparando cualquiera que sea el tipo de items[index].instanceData es y una char*.

Le sugiero que poner un poco de registro en el operador y ver si realmente está siendo llamado -. Sospecho que no es

Una de las opciones para tomar el operador == fuera de la ecuación temporal sería hacer la comparación explícita:

 if (strcmp(items[index].instanceData.getName(), key) == 0)
 {
     ...
 }

En otro punto, no puedo ver cómo esto es en realidad haciendo una búsqueda binaria en absoluto. A mi me parece como que es sólo una lista simple -. Que está haciendo una búsqueda lineal dentro retrieve en lugar de comparar la llave y yendo hacia la izquierda o hacia la derecha por el árbol (o regresar "encontrado") en función del resultado

Answer 3

No puedo decir con seguridad sin ver el código de BST, pero esto se ve mal:

for(int index=0; index < maxsize+1; index++)

Con las convenciones tradicionales, que debe ser:

for(int index=0; index < maxsize; index++)

Además de eso, también parece que su función sea devuelve verdadero o algún booleano indefinido. Probablemente debería tener un return false; al final de BST :: recuperar.