1

キー値を再帰的に使用して単語を検索しようとしています。検索機能: 問題は、インデックスが 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;

}

ここに私のヘッダーファイルの1つがあります..

 #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;


}
4

1 に答える 1

2

0,1,3,7,8になるはずです

なぜあなたはこの行動を期待していますか？それは「バイナリ」検索ではありません。7 の左の子は 15、右の子は 16 になります。8 は 3 の右の子です。

あなたのコードは正しいようです。結果は正しいようです。欠陥があるように見えるのはあなたの期待です。

于 2009-12-06T20:09:06.997 に答える