Funzione di ricerca ricorsiva dell'albero di ricerca binario C++

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

Quindi questa è la mia funzione di ricerca per la mia classe BST con un nodo T.x sono i dati cercati all'interno dell'albero, len è solo la quantità di nodi che deve percorrere per trovare il nodo corrispondente, se esiste.Non l'ho ancora implementato, sto solo sviluppando in modo incrementale il mio incarico.Lo chiamo così:

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

v è solo un vettore che ho dovuto creare per confrontarlo, quindi gli sta semplicemente fornendo un int.L'errore che ricevo:

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]

Quindi non sono sicuro di cosa sto facendo di sbagliato o dove sto sbagliando.

Answer 1

Va bene, bool BST<T>::search(struct Node<T>*& root, const T& x) probabilmente dovrebbe essere const dopo in questo modo: bool BST<T>::search(struct Node<T>*& root, const T& x) const.Fondamentalmente, hai chiamato una funzione non const da una funzione const e questo è un no-no.

A proposito, questo mi sembra sospetto "struct Node<T>*&"...Probabilmente lascerei cadere & e lavorerei con Node<T>*...ma forse ne hai bisogno a causa del struttura?

Inoltre, questo è C++, non c'è motivo di lasciare Node come struttura...bisogno di avere struttura nella definizione dei parametri sembra proprio pessimo, IMHO.Perché non rendere Node una classe?

Answer 2

Esistono diversi problemi nel codice di ricerca:

• L'ordinamento è all'indietro, se i dati del nodo sono inferiori a quello che si cerca, è necessario cercare nel ramo destro, non nel ramo sinistro.

• Dovresti restituire il risultato della chiamata ricorsiva

• Non è inoltre chiaro il motivo per cui si passa root per riferimento. dovrebbe invece essere passato come const puntatore qualificato e anche il corpo del metodo dovrebbe essere <=> qualificato.

Ecco un'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);
}

Ed ecco un'implementazione non ricorsiva più semplice:

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. Prendi i dati del valore del nodo;
2. Ripeti i passaggi da 3 a 5 fino a quando non troviamo il valore o andiamo oltre l'albero.
3. Se i dati sono uguali al valore del nodo radice, la ricerca ha esito positivo e termina l'algoritmo.
4. Se i dati sono inferiori al valore del nodo principale, è necessario cercare il sottoalbero di sinistra.
5. Altrimenti i dati sono inferiori al valore del nodo radice, dobbiamo cercare l'albero secondario sinistro.
6. Stampa messaggio di uscita " Trovato " o " Non trovato " ;.

---

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