função de pesquisa C ++ binário Pesquisa árvore recursiva

Question

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

Assim, esta é a minha função de pesquisa para minha classe BST com um nó T. x é o ser dados procurou dentro da árvore, len é apenas a quantidade de nós que tem que viajar para chegar com o nó correspondente, se existir. Eu não implented que ainda, estou apenas de forma incremental desenvolver meu trabalho. Eu estou chamando-o ao fazer isso:

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

v é apenas um vetor eu tive que criar a compará-lo, e por isso este é apenas fornecendo-o com um int. O erro que estou recebendo:

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]

Então, eu não sei o que estou fazendo de errado ou onde eu estou fazendo errado.

Answer 1

Ok, bool BST<T>::search(struct Node<T>*& root, const T& x) provavelmente deve ter const após ele assim: bool BST<T>::search(struct Node<T>*& root, const T& x) const. Basicamente, você chamou uma função não-const de uma função const e este é um não-não.

BTW, isso parece suspeito para mim "struct Node<T>*&" ... eu provavelmente largar o & e trabalhar com Node<T>* ... mas talvez você precisa que, devido à struct ?

Além disso, este é C ++, não há razão para deixar Node como um struct ... a necessidade de ter struct na definição do parâmetro apenas parece ruim, IMHO. Por que não fazer Node uma classe?

Answer 2

Existem vários problemas no seu código de pesquisa:

• A ordem de classificação é para trás, se os dados nó é menor do que o que você procurar, você deve procurar no ramo direito, e não o ramo esquerdo.

• Você deve retornar o resultado da chamada recursiva

• Também não está claro por que você passar root por referência. Ao contrário, deve ser passado como um ponteiro qualificado const e o corpo do método deve ser const qualificados também.

Aqui está uma alternativa:

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

E aqui é uma implementação não recursiva simples:

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

Answer 3

Algoritmo:

1. Tome dados valor do nó;
2. Repita a etapa 3 para a etapa 5 até encontrarmos o valor ou nós vamos além da árvore.
3. Se os dados é igual ao valor do nó raiz, a busca é bem sucedida e encerrar o algoritmo.
4. Se os dados é menor que o valor nó raiz, temos de procurar a árvore sub esquerda.
5. Dados Else é inferior ao valor nó raiz, temos de procurar a árvore sub esquerda.
6. Saída Imprimir mensagem "Found" ou "Not Found".

---

implementação 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);
   }