c++ - 搜索二叉搜索树 - 基于数组

Question

我正在尝试使用键值递归地搜索单词。在检索功能中:问题是索引从 0、1、3、7 到 15……它应该是 0、1、3、7、8 等等我的插件按预期工作。我有订单，预订单，一切正常。有人可以帮我解决这个问题吗？我已经为此工作了 4 天了!我知道它是从左到右的。问题是它不会在左后右走。我只会添加我认为您需要帮助我的函数和代码。我正在使用 2 retireve 进行递归。

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

retrieve(key, aData, parent);

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

}

其他检索

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;

} 
}

==运算符函数..

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

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

}

这是我的头文件之一..

 #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

main() 函数的一部分..

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

和

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

为什么你会期待这种行为？这根本不是“二进制”搜索。 7 的左 child 将是 15，右 child 将是 16。8 是 3 的右 child 。

您的代码看起来是正确的。您的结果看起来是正确的。您的期望似乎有缺陷。