2 
template <class T>
bool BST<T>::search(const T& x, int& len) const
{
    return search(BT<T>::root, x);
}


template <class T>
bool BST<T>::search(struct Node<T>*& root, const T& x)
{
   if (root == NULL)
       return false;
   else
      {
         if (root->data == x)
             return true;
         else if(root->data < x)
             search(root->left, x);
         else 
             search(root->right, x);                 
      }             
}

これは、T ノードを持つ BST クラスの検索関数です。x はツリー内で検索されるデータです。len は、一致するノードが存在する場合にそれを見つけるために移動しなければならないノードの数です。私はまだそれを実装していません。私は自分の課題を段階的に開発しているだけです。私はこれを行うことでそれを呼び出しています:

if(t.search(v[1], len) == true)
       cout << endl << "true";

v は、比較するために作成しなければならなかった単なるベクトルなので、これは単に int を指定するだけです。私が得ているエラー：

BST.h: In member function âbool BST<T>::search(const T&, int&) const [with T = int]â:
prog5.cc:24:   instantiated from here    
BST.h:78: error: no matching function for call to âBST<int>::search(Node<int>* const&, const int&) constâ    
BST.h:76: note: candidates are: bool BST<T>::search(const T&, int&) const [with T = int]
BST.h:83: note:                 bool BST<T>::search(Node<T>*&, const T&) [with T = int]

そのため、自分が何を間違っているのか、どこが間違っているのかわかりません。

4

3 に答える 3

2

さて、bool BST<T>::search(struct Node<T>*& root, const T& x)おそらくその後に const があるはずです: bool BST<T>::search(struct Node<T>*& root, const T& x) const. 基本的に、const 関数から非 const 関数を呼び出しましたが、これはノーノーです。

ところで、これは私には疑わしいように見えます " struct Node<T>*&"...私はおそらく & を削除して操作します...しかし、構造体Node<T>*のためにそれが必要なのかもしれません?

また、これは C++ です。Node を構造体のままにしておく理由はありません...パラメーター定義に構造体が必要なのが見た目が悪いだけです。Node をクラスにしてみませんか?

于 2008-10-29T02:49:38.763 に答える
1

検索コードには複数の問題があります:

  • ソート順は逆です。ノード データが検索対象より少ない場合は、左側のブランチではなく右側のブランチを検索する必要があります。

  • 再帰呼び出しの結果を返す必要があります

  • rootまた、参照渡しの理由も不明です。代わりにconst修飾ポインターとして渡す必要があり、メソッド本体もconst修飾する必要があります。

代替案は次のとおりです。

template <class T>
bool BST<T>::search(const struct Node<T> *root, const T& x) const {
    if (root == NULL)
        return false;
    else
    if (root->data == x)
        return true;
    else
    if (root->data < x)
        return search(root->right, x);
    else 
        return search(root->left, x);
}

そして、これはより単純な非再帰的な実装です:

template <class T>
bool BST<T>::search(const struct Node<T> *root, const T& x) const {
    while (root != NULL) {
        if (root->data == x)
            return true;
        if (root->data < x)
            root = root->right;
        else 
            root = root->left;
    }
    return false;
}
于 2016-10-31T20:18:03.623 に答える
0

アルゴリズム :

  1. ノード値データを取得します。
  2. 値が見つかるまで、またはツリーを超えるまで、ステップ 3 からステップ 5 を繰り返します。
  3. data が root node value と等しい場合、検索は成功し、アルゴリズムを終了します。
  4. データがルート ノードの値より小さい場合、左側のサブツリーを検索する必要があります。
  5. それ以外の場合、データがルート ノードの値より小さい場合、左側のサブツリーを検索する必要があります。
  6. Output メッセージ「Found」または「Not Found」を出力します。

C++ 実装

    node* search(node* root, int data)
    {
     if (root==NULL || root->data==data) return root;

     if (root->data < data)   return search(root->right, data);

     return search(root->left, data);
   }
于 2016-10-05T18:30:25.133 に答える