0

私は文字通り、この 1 つのフェラで髪を引き裂いています。これが問題です。2-3 ツリーをハードコーディングし、現在のノードの値を出力する順序トラバーサル関数を使用して動作することを確認しました。したがって、ツリーが正しく構築されていることがわかります。

 Node *r;
  Node zero,one,two,three,four,five,six,seven,eight,nine,ten;
  r = &zero;

          //Root
 zero.small = 50;
 zero.large = 90;
 zero.left = &one;       //Child node to the left
 zero.middle = &four;    //Child node in the middle
 zero.right = &seven;    //Child node to the right

  //Left Tree
 one.small = 20;
 one.large = NULL;
 one.left = &two;
 one.middle = NULL;
 one.right = &three;

 two.small = 10;
 two.large = NULL;
 two.left = NULL;
 two.middle = NULL;
 two.right = NULL;

 three.small = 30;
 three.large = 40;
 three.left = NULL;
 three.middle = NULL;
 three.right = NULL;

  //Middle Tree
 four.small = 70;
 four.large = NULL;
 four.left = &five;
 four.middle = NULL;
 four.right = &six;

 five.small = 60;
 five.large = NULL;
 five.left = NULL;
 five.middle = NULL;
 five.right = NULL;

 six.small = 80;
 six.large = NULL;
 six.left = NULL;
 six.middle = NULL;
 six.right = NULL;

  //Right Tree
 seven.small = 120;
 seven.large = 150;
 seven.left = &eight;
 seven.middle = &nine;
 seven.right = &ten;

 eight.small = 100;
 eight.large = 110;
 eight.left = NULL;
 eight.middle = NULL;
 eight.right = NULL;

 nine.small = 130;
 nine.large = 140;
 nine.left = NULL;
 nine.middle = NULL;
 nine.right = NULL;

 ten.small = 160;
 ten.large = NULL;
 ten.left = NULL;
 ten.middle = NULL;
 ten.right = NULL;

 cout<<"inorder traversal for debug"<<endl;
 inOrder(*r);

出力は次のようになります: 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160

したがって、ツリーが正しく構築されていることが証明されます。ツリー内の値を検索するようにコードを変更するように依頼されました。そのため、この関数を以下に書きました。これは基本的に、順序トラバーサル関数から出力を差し引いたものであり、検索キーがツリーで見つかった場合に TRUE を返す単純な if ステートメントです。

bool retrieve(Node r, int key)
{
 if (r.left)
    retrieve(*r.left, key);
 if (r.small)
 {
     if (r.small == key)
    {
        cout<<"The node: "<<r.small<<" is equal to search key: "<<key<<endl; //for debug purposes
        return true;
    }
 }
 if (r.middle)
    retrieve(*r.middle, key);
 if (r.large)
 if (r.right)
    retrieve(*r.right, key);  
}

ユーザーは検索する番号 (int キー) の入力を求められ、入力時に if ステートメントを入力します。

if (retrieve(*r, key))
 {
     cout<<key<<" is found!"<<endl;
 }
 else
     cout<<key<<" is not found!"<<endl;

ここでの問題は、これは論理的には正しいように思えますが、値「85」(ツリーにはまったく配置されていません) を入力すると、プログラムは「85 が見つかりました!」と出力することです。関数内にある COUT ステートメントが出力されていないことに注意してください。cout<<"The node: "<<r.small<<" is equal to search key: "<<key<<endl;プログラムをデバッグしてステップ実行しましたが、bool 関数 (取得) が常に true を返すものに関係なく...何ですか? そのため、ブール関数の if ステートメントを切り替えて、「60」(ツリー上にある) を入力すると false (デバッグ目的のみ) を返すようにしましたが、ブール関数は引き続き true を返します。わずかに異なるコードの組み合わせをいくつか試しましたが、役に立ちませんでした..一体何が起こっているのですか??

前もって感謝します、

タイラー

4

3 に答える 3

0

少なくともノードであるため、再帰を停止する必要があるかどうかを確認するための初期テストが必要です。

// precondition: current is not 0
// returns: true or false. If true, location is set to the node 
// where it was found.
bool DoSearch(Node *current, int key, Node *location)
{
 /*
  * Is key in current?
  */
if (current->smallValue == key || (current->isThreeNode() 
       && current->largeValue == key)) {

    location = current;
    return true;

} else if ((current->isLeafNode())) {

    location = current;
    return false;
 /*
  *  Does current have two keys?
  */
} else if (current->isThreeNode()){

    if (key < current->smallValue) {

        DoSearch(key, current->leftChild, location);

    }  else if (key < current->largeValue) {

        DoSearch(key, current->middleChild, location);

    } else {

        DoSearch(key, current->rightChild, location);
    }

} else { // ...or only one?

     if (key < current->smallValue) {

        DoSearch(key, current->leftChild, location);

    }  else {

        DoSearch(key, current->rightChild, location);
    }
}
}
于 2013-05-14T01:39:36.323 に答える
0

if (r.small == key)ブランチを除いて、値を返すことはありません。

2–3 ツリー - ウィキペディアから、コードは最初にとキーを比較keyし、比較に応じて から結果を返す必要があると思います。smalllargeretrieve(*r.left/middle/right, key)

これらの線に沿ったもの (未テスト)

if (key < r.small)
    return retrieve(*r.small, key);

if (key == r.small)
    return TRUE;

if (r.right == NULL)
    return retrieve(*r.middle, key);

if (key < r.large)
    return retrieve(*r.middle, key);

if (key == r.large)
    return TRUE;

return retrieve(*r.right, key);
于 2013-04-07T21:17:42.840 に答える