Compare string against objects in binary search tree

Question

Looking for help. As I am trying to get user's input, which is string. Then, compare the string that matched the word variable in myBST then print out. Unfortunately, my binary search tree holds a class named WordApp, that consists of int frequency; string word.

Which I am trying to compare user input that match with word variable from WordApp object, but I do not have direct access to it. Here is the definition of WordApp.

class WordApp{
int frequency;
string word;

string processText(string &);
public:
void setWord(string);
void setFrequency(int);

string getWord();
int getFrequency();

void scanText();

WordApp();

bool operator>(WordApp);
friend ostream& operator <<(ostream& out, WordApp result) //To overload "<<" cout operator in order to use .inOrderPrint()
{
    out << "(" << result.word << ", " << result.frequency << ")" << endl;
    return out;
}
bool WordApp::operator>(WordApp result) //To overload ">" greater than        operator that used in BST class, insert()
{
if (this->frequency > result.getFrequency())
{
    return 1;
}
else if (this->frequency == result.getFrequency())
{
    if (this->word.compare(result.word) > 0)
    {
        return 1;
    }
}
return 0;}

In my binary search tree, which I have declared as below to store WordApp objects

WordApp myWord;
BST<WordApp> myBST;
myBST.insert(myWord);
string input;
cout << "Query: ";
cin >> input;
cout << myBST.Traversal(input) << endl; //search function doesn't take string as argument since myBST<WordApp> but not myBST<string>

While below is my Traversal function implemented in binary search tree

template<class T>
bool BST<T>::Traversal(T result)
{
if (root == NULL)
{
    return 0;
}

Traversal2(root, result);
return 1;
}

template<class T>
bool BST<T>::Traversal2(BTNode<T> *cursor, T result)
{
if (cursor == NULL)
{
    return;
}
if (cursor->item > result)
{
    Traversal2(cursor->left, result);
}
else
{
    Traversal2(cursor->right, result);
}
return cursor->item;
}

As statement myBST.search(input) is comparing an input a string variable to a object class, which is unrecognized. I tried to think but getting nowhere. Can anyone please help on this?

Answer 1

First I want to point this out, since return type of you your function is bool it would be much more clear to return true/false instead of 1/0.

Secondly your problem is with traversal function, right? In your provided code it returns bool (which was meant to indicate if value exists?), but later on you mention, or at least i assumed, you want to return actual value if it is present. Best choice for this is to return pointer (or nullptr in case item is not present in tree). Let's look at declaration of traversal function then:

// now it returns pointer instead of bool
// added const& to argument type cause cause it suits this example better
// return type is T*, suits example the best
template<class T>
T* BST<T>::traversal(const T& result); 

I'm sure everything is pretty clear right now. There lies a first problem in your example: Your BST tree is templated by WordApp, therefore you could view above function as this in you code:

template<>
WordApp* BST<WordApp>::traversal(const WordApp& result);

Well this can't really work, can it? You are expecting type WordApp, but you are passing std::string instead in your example of main. You haven't defined conversion from string nor ctor that could handle it. It should work if you defined ctor that takes string as parameter:

template <typename T>
class WordApp {
    int frequency = 0;
    std::string word;
    // ...
public:
    WordApp() noexcept = default;
    WordApp(const std::string& w) // < this is new
        : word(w) {}
    // ...
}

Let's move on to the actual algorithm of traversal function. Binary trees are very good structures that can utilize recursion pretty well. You did not really show BTNode class so I assume it can look like this:

template <typename T>
struct BTNode {
    T item;
    std::unique_ptr<BTNode> left;
    std::unique_ptr<BTNode> right;
    // maybe some other functions
}

template <typename T>
class BST {
    std::unique_ptr<BTNode<T>> root;
public:
    // ...
}

You question might be, what is this std::unique_ptr class? The answer is in provided link. TL;DR: It manages raw pointer, and deletes it automatically when destructor of std::unique_ptr is called. VERY useful thing, look into it. Note that it is usable only if you compile at standard of c++11 or higher.

However let's move on. I was talking about recursion so I add function which gets called from traversal function above:

template<class T>
T* BST<T>::traversal(const T& result) {
    return _traversal(root.get(), result);
}

template<class T>
T* BST<T>::_traversal(BTNode<T>* ptr, const T& result) {
    if (!ptr)
        return nullptr;
    // you need to test this! otherwise you just traverse to the Tree leaves without finding anything
    if (ptr->item == result) 
        return &ptr->item;
    if (ptr->item > result) {
        return _traversal(ptr->left.get(), result);
    } else {
        return _traversal(ptr->right.get(), result);
    }
}

I'm sure you noticed I added operator== which is clearly not defined for WordApp but in your example you never actually test if you found what you are looking for. You first test it if it's greater than result, and then nothing is tested in else branch. to fix it you either implement operator == and test it before, or just implement operator < and test it in else branch.

Also I would recommend implementing template classes in headers (you should look into that if you don't know why) and within class' declaration cause then its function are implicitly inlined. If you are interested we can move this question out of stackoverflow and just look into improving your C++ coding in general. I hope I helped a bit even though more than answering I pointed out some of major mistakes I saw. Feel free to correct me if I missed something or just got the bad idea what you meant in your provided code. Feel free to ask questions as well!