C ++ Двоичное дерево поиска Рекурсивная функция поиска - PullRequest
Новая
       9

C ++ Двоичное дерево поиска Рекурсивная функция поиска

2 голосов
/ 29 октября 2008 
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 - это просто вектор, который я должен был создать, чтобы сравнить с ним, и поэтому он просто предоставляет ему 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]

Так что я не уверен, что я делаю неправильно или где я делаю неправильно.

Ответы [ 3 ]

2 голосов
/ 29 октября 2008

Хорошо, 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>* ... но, возможно, вам это нужно из-за struct ?

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

1 голос
/ 31 октября 2016

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

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

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

  • Также неясно, почему вы передаете 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;
}
0 голосов
/ 05 октября 2016

Алгоритм:

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

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