Doug Doug - 2 months ago 16
C++ Question

C++ Binary Search Tree Recursive search function

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


So this is my search function for my BST class with a T node. x is the data being searched for within the tree, len is just the amount of nodes it has to travel to come up with the matching node if it exists. I have not implented that yet, I'm just incrementally developing my assignment. I'm calling it by doing this:

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


v is just a vector I had to create to compare it to, and so this is just supplying it with an int. The error I'm getting:

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]


So I'm not sure what I'm doing wrong or where I'm doing wrong.

Answer

Okay, bool BST<T>::search(struct Node<T>*& root, const T& x) should probably have const after it like so: bool BST<T>::search(struct Node<T>*& root, const T& x) const. Basically, you've called a non-const function from a const function and this is a no-no.

BTW, this looks suspect to me "struct Node<T>*&"... I'd probably drop the & and work with Node<T>*... but maybe you need that because of the struct?

Also, this is C++, there is no reason to leave Node as a struct... needing to have struct in the parameter definition just looks bad, IMHO. Why not make Node a class?