C ++バイナリ検索ツリーの再帰検索機能

StackOverflow https://stackoverflow.com/questions/245628

  •  05-07-2019
  •  | 
  •  

質問 

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]

だから、私は何を間違っているのか、どこで間違っているのかわからない。

役に立ちましたか？

解決

さて、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関数を呼び出しましたが、これはノーです。

ところで、これは私には疑わしいようです<！> quot; struct Node<T>*& <！> quot; ...おそらく<！> amp;を落とすでしょう。 Node<T>* ...で作業しますが、 struct のせいで必要になるかもしれません。

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

他のヒント

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

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

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

  • rootを参照渡しする理由も不明です。代わりに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;
}

アルゴリズム：

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

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);
   }
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top