Función de búsqueda recursiva del árbol de búsqueda binaria de 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);                 
      }             
}

Esta es mi función de búsqueda para mi clase BST con un nodo T.x son los datos que se buscan dentro del árbol, len es solo la cantidad de nodos que tiene que recorrer para encontrar el nodo coincidente, si existe.Aún no lo he implementado, solo estoy desarrollando mi tarea de manera incremental.Lo llamo haciendo esto:

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

v es solo un vector que tuve que crear para compararlo, por lo que esto solo le proporciona un int.El error que recibo:

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]

Así que no estoy seguro de qué estoy haciendo mal ni dónde lo estoy haciendo mal.

Answer 1

Bien, bool BST<T>::search(struct Node<T>*& root, const T& x) probablemente debería tener constante después de esto, así: bool BST<T>::search(struct Node<T>*& root, const T& x) const. Básicamente, ha llamado una función no const desde una función const y esto es un no-no.

Por cierto, esto me parece sospechoso " struct Node<T>*& " ... probablemente dejaría caer el amplificador &; y trabaje con Node<T>* ... pero tal vez lo necesite debido a la estructura ?

Además, esto es C ++, no hay razón para dejar Node como una estructura ... la necesidad de tener struct en la definición del parámetro simplemente se ve mal, en mi humilde opinión. ¿Por qué no hacer de Node una clase?

Answer 2

Hay varios problemas en su código de búsqueda:

• El orden de clasificación es al revés, si los datos del nodo son menores que lo que busca, debe buscar en la rama derecha, no en la rama izquierda.

• Deberías devolver el resultado de la llamada recursiva.

• Tampoco está claro por qué pasas root por referencia.en cambio, debería pasarse como un const puntero calificado y el cuerpo del método deben ser const calificado también.

Aquí hay una 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);
}

Y aquí hay una implementación no recursiva más 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

Algoritmo:

1. Tomar datos de valor de nodo;
2. Repita del paso 3 al paso 5 hasta encontrar el valor o ir más allá del árbol.
3. Si los datos son iguales al valor del nodo raíz, la búsqueda es exitosa y termina el algoritmo.
4. Si los datos son menores que el valor del nodo raíz, tenemos que buscar el subárbol izquierdo.
5. De lo contrario, los datos son inferiores al valor del nodo raíz, tenemos que buscar el subárbol izquierdo.
6. Salida Imprimir mensaje " Encontrado " o " No encontrado " ;.

---

Implementación de 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);
   }