C++ Binary Search Tree Функция рекурсивного поиска

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);                 
      }             
}

Итак, это моя функция поиска моего класса BST с T-узлом. x — это данные, которые ищутся в дереве, len — это просто количество узлов, которые необходимо пройти, чтобы найти соответствующий узел, если он существует. Я еще не реализовал это, я просто постепенно развиваю свое задание. Я вызываю это, делая это:

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

v — это просто вектор, который я должен был создать, чтобы сравнить его с ним, и поэтому он просто снабжает его целым числом. Ошибка, которую я получаю:

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]

Поэтому я не уверен, что я делаю неправильно или где я делаю неправильно.


c++ binary-search-tree
person Doug    schedule 29.10.2008    source источник
comment
Отсутствуют огромные куски информации. Что такое BT‹T›::root? BST и BT это одно и то же? узел и узел одно и то же? Пожалуйста, вырежьте и вставьте, не печатайте.   -  person    schedule 29.10.2008
comment
ну, это часть производной функции, поэтому, чтобы передать корневой узел, я должен указать ему конкретно BT‹T›::root, иначе я получаю ошибки.   -  person Doug    schedule 29.10.2008
comment
Я получаю, что root не был объявлен в этой области, если я этого не сделаю.   -  person Doug    schedule 29.10.2008

Ответы (3)


arrow_upward
2
arrow_downward

Хорошо, bool BST<T>::search(struct Node<T>*& root, const T& x), вероятно, должен иметь const после него, например: bool BST<T>::search(struct Node<T>*& root, const T& x) const. По сути, вы вызвали неконстантную функцию из константной функции, и это нет-нет.

Кстати, мне это кажется подозрительным "struct Node<T>*&"... Я бы, наверное, отказался от & и работал с Node<T>*... но, может быть, вам это нужно из-за структуры?

Кроме того, это C++, нет причин оставлять Node как структуру... необходимость иметь struct в определении параметра просто выглядит плохо, ИМХО. Почему бы не сделать Node классом?

person paxos1977    schedule 29.10.2008
comment
Я вставил полное сообщение. Но раньше с форматированием было не очень хорошо, поэтому я вырезал его, но вставил обратно. - person Doug; 29.10.2008
comment
Это класс узлов, но по какой-то причине, чтобы получить к нему доступ таким образом, мне пришлось сделать его структурой в функциях вставки и поиска. Это то, что мне предоставили через википедию и мой проф. - person Doug; 29.10.2008

arrow_upward
1
arrow_downward

В вашем поисковом коде несколько проблем:

  • Порядок сортировки обратный, если данных узла меньше, чем то, что вы ищете, вы должны искать в правой ветви, а не в левой.

  • Вы должны вернуть результат рекурсивного вызова

  • Также непонятно, почему вы передаете 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;
}
person chqrlie    schedule 31.10.2016
comment
Спасибо за нерекурсивную версию. - person Aminos; 02.03.2017

arrow_upward
0
arrow_downward

Алгоритм:

  1. Возьмите данные о значении узла;
  2. Повторяем шаги с 3 по 5, пока не найдем значение или не выйдем за пределы дерева.
  3. Если данные равны значению корневого узла, поиск считается успешным и алгоритм завершает работу.
  4. Если данные меньше, чем значение корневого узла, мы должны искать в левом поддереве.
  5. В противном случае данные меньше, чем значение корневого узла, мы должны искать в левом поддереве.
  6. Выходные данные Вывести сообщение «Найдено» или «Не найдено».

Реализация С++

    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);
   }
person rashedcs    schedule 05.10.2016
comment
Можете ли вы добавить контекст? - person mjk; 05.10.2016
comment
Tnq за то, что нашел мою ошибку. Маркус Мюллер - person rashedcs; 31.10.2016