C ++ Binary Search Tree Fonction de recherche récursive

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

C’est donc ma fonction de recherche pour ma classe BST avec un nœud T. x correspond aux données recherchées dans l'arborescence, len correspond simplement au nombre de nœuds qu'il doit parcourir pour trouver le nœud correspondant, s'il existe. Je ne l'ai pas encore implanté, je développe mon travail progressivement. Je l'appelle en faisant ceci:

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

v n’est qu’un vecteur que je devais créer pour le comparer, c’est pourquoi nous le fournissons simplement avec un int. L'erreur que je reçois:

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]

Je ne suis donc pas sûr de ce que je fais mal ou de ce que je fais mal.

Answer 1

D'accord, bool BST<T>::search(struct Node<T>*& root, const T& x) devrait probablement avoir const après, comme suit: bool BST<T>::search(struct Node<T>*& root, const T& x) const. Fondamentalement, vous avez appelé une fonction non-const à partir d'une fonction const, ce qui est un non-non.

BTW, cela me semble suspect & "; struct Node<T>*& &"; ... je supprimerais probablement le & ampli; et travailler avec Node<T>* ... mais peut-être en avez-vous besoin à cause de la structure ?

En outre, il s’agit de C ++, il n’ya aucune raison de laisser Node en tant que structure ... nécessitant la présence de structure dans la définition du paramètre, mais à mon humble avis, elle est mauvaise. Pourquoi ne pas faire de Node une classe?

Answer 2

Il existe plusieurs problèmes dans votre code de recherche:

• L'ordre de tri est inversé. Si les données du nœud sont inférieures à celles que vous recherchez, vous devez effectuer une recherche dans la branche droite, pas dans la branche gauche.

• Vous devez renvoyer le résultat de l'appel récursif

• La raison pour laquelle vous passez root par référence n’est pas claire non plus. il doit plutôt être passé en tant que pointeur qualifié const et le corps de la méthode doit également être <=> qualifié.

Voici une alternative:

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

Et voici une implémentation non récursive plus simple:

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

Algorithme:

1. Prendre des données de valeur de nœud;
2. Répétez les étapes 3 à 5 jusqu'à ce que nous trouvions la valeur ou que nous allions au-delà de l'arbre.
3. Si les données correspondent à la valeur du noeud racine, la recherche aboutit et met fin à l'algorithme.
4. Si les données sont inférieures à la valeur du noeud racine, vous devez effectuer une recherche dans la sous-arborescence de gauche.
5. Si les données sont inférieures à la valeur du nœud racine, nous devons rechercher le sous-arbre de gauche.
6. Message d'impression en sortie " Trouvé " ou " non trouvé ".

Implémentation 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);
   }