이진 검색 트리를 검색하십시오

Question

키 안에서 이름을 찾으려고 노력하고 있습니다. 나는 그것이 그것을 잘 회수하고 있다고 생각합니다. 그러나 발견되지 않은대로 나타납니다. 어딘가에 내 코드가 잘못되었을까요?

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

안에 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);

기능 검색 ...

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
        }


    }

}


 }

Data.cpp에 정의됩니다

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

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

}

따라서 Main () 내부 의이 코드는 올바르게 작동해야한다고 생각할 때 찾을 수없는 곳입니다. 이름과 Adata는 모두 발견 된 올바른 이름을 포함합니다 ..

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

BST를 사용하여 트리를 탐색해야합니다. 다른 사람들이 말한 것처럼 배열의 각 항목을 반복하지 마십시오. 다음과 같은 것을 시도하십시오.

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)

잘 작동해야합니다! :)

Answer 2

저는 C ++ 전문가가 아니지만 귀하의 == 운영자가 실제로 평가되고 있습니까? 그것은 두 개의 const 데이터 참조를 취하기위한 것이지만, 당신은 items[index].instanceData 그리고 a char*.

운영자에 로그를 넣고 실제로 호출되는지 확인하는 것이 좋습니다.

== 연산자를 일시적으로 방정식에서 꺼내는 한 가지 옵션은 비교를 명시 적으로 만드는 것입니다.

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

다른 시점에서, 나는 이것이 실제로 어떻게 이진 검색을 수행하는지 알 수 없습니다. 그것은 단지 평범한 목록 인 것처럼 보입니다. 당신은 내에서 선형 검색을하고 있습니다. retrieve 키를 비교하고 결과에 따라 나무를 왼쪽 또는 오른쪽으로 내려 오는 대신 (또는 "발견").

Answer 3

BST 코드를 보지 않고는 확실히 말할 수 없지만 이것은 잘못 보입니다.

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

전통적인 규칙을 사용하면 다음과 같아야합니다.

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

그 외에도, 그것은 또한 당신의 기능이 True 또는 일부 정의되지 않은 부울을 반환하는 것 같습니다. 당신은 아마 A.가 있어야합니다 return false; bst :: 검색의 끝에서.