Searching a Binary Search Tree - Array Based

Question

I am trying to search for a word using a key value recursively. In retrieve function: Problem is the index goes from 0, 1,3,7, to 15.... it suppose to go 0,1,3,7,8 and so forth I have the insert working as expected. I have the inorder, preorders, all working. Can someone please help me figure out this problem? I have been working on this for 4 days now! I understand it goes left to right. Problem is it wont go right after left. I will only add the functions and code i think you will need to help me.. I am using 2 retireve for doing a recursive..

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

retrieve(key, aData, parent);

if (key == aData)
{
    return true;
}
else
{
    return false;
}

}

the other retrieve

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


if (!items[parent].empty )
{

    if (key == items[parent].instanceData.getName())
    {
        aData.setName(key);
        return true;
    }
    else if (key < items[parent].instanceData.getName() ) // changed -- now goes from 0,2,6 suppose to go to o,2,5
    {
        parent =(2*parent) + 1;
        retrieve(key, aData, parent);
    }
    else
    {
        parent =( 2*parent) + 2;
        retrieve(key, aData, parent);
    }
//  return 0;

} 
}

==operator function..

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

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

}

and here is one of my header files..

 #include "data.h"

 class BST                               
 {
 public:
BST(int capacity = 5);              // constructor (default if no arg supplied)
BST(const BST& aTable);             // copy constructor
~BST();                             // destructor

void insert(const data& aData);     
bool remove(const char *key);
bool retrieve(const char *key, data& aData) const;
void displayArrayOrder(ostream& out) const;     
void displayPreOrder(ostream& out) const;
void displayInOrder(ostream& out) const;
void displayPostOrder(ostream& out) const;
int getSize(void) const;

    private:

  int size;
  int maxsize;  
  int parent;


  void expand();

struct item
{
    bool    empty;
    data instanceData;
    bool  isLeaf;
};

item *items;

void insert(int index, const data & aData ); 
void displayHeaders(ostream& out)const;
void BST::displayPreOrder(std::ostream &out, int parent)const;
void BST::displayInOrder(std::ostream &out, int parent)const;
void BST::displayPostOrder(std::ostream &out, int parent)const;
bool BST::retrieve(const char *key, data& aData, int parent) const;
void itemsPrinted(ostream &out,int size)const;
  };


 #endif // BST_H

part of the main() function..

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);    // calls search function..

and

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

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


}

Answer 1

it suppose to go 0,1,3,7,8

Why are you expecting this behaviour? That's not a "binary" search at all. The left child of 7 will be 15, the right child will be 16. 8 is the right child of 3.

Your code looks correct. Your results look correct. It's your expectations that appear flawed.