Doug Doug - 10 months ago 52
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;
if (root->data == x)
return true;
else if(root->data < x)
search(root->left, x);
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([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]â: 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 Source

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?