Двоичное дерево поиска C++. Функция рекурсивного поиска.
-
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);
}
}
Итак, это моя функция поиска для моего класса 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]
Поэтому я не уверен, что я делаю неправильно и где я делаю неправильно.
Решение
Хорошо, 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>*&
" ... Я бы, вероятно, отбросил & amp; и работать с Node<T>*
... но, может быть, вам это нужно из-за struct ? Р>
Кроме того, это C ++, нет причин оставлять Node в качестве структуры ... необходимо, чтобы struct в определении параметра выглядело просто плохо, ИМХО. Почему бы не сделать Node классом?
Другие советы
В вашем поисковом коде есть несколько проблем:
Порядок сортировки обратный: если данные узла меньше тех, которые вы ищете, вам следует искать в правой, а не в левой ветке.
Вы должны вернуть результат рекурсивного вызова
Также непонятно, почему вы проходите
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;
}
Алгоритм .
<Ол>реализация 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);
}