CODEWITHSUNDEEP
c++operator-overloadingbinary-search-tree
aelarabi
aelarabi

Reputation: 51

Overloading << operator as a "friend" function to print BST - C++

I am attempting to overload the << operator to print out the private data of a BST (contains both a word and a count). I am required to make this operator a friend non-member function of my WordTree class, and cannot define any additional public member functions (this is a school assignment).

Here is my operator<< friend function:

ostream& operator<<(ostream &out, const WordTree& rhs)
{
    out << InOrder(&out, rhs.root); // does not work as InOrder is private member function
    return out;
}

And this is my private function InOrder that performs an in-order traversal on the BST.

ostream& WordTree::InOrder(ostream &out, WordNode* cur)
{
    if (cur != nullptr)
    {
        InOrder(out, cur->m_left);
        out << cur->m_data << " " << cur->m_count << endl;
        InOrder(out, cur->m_right);
    }

    return out;
}

What are some ways I can approach this problem?

Upvotes: 0

Views: 1684

Answers (2)

PaulMcKenzie
PaulMcKenzie

Reputation: 35440

What are some ways I can approach this problem?

This may be a little advanced, but you asked the question, and here is a possible way to approach the problem:

InOrder could be a generic in-order traversal function, and whatever you want to do with the node that is visited, you pass that node to a user-defined function. That would have made your traversal much more generic and useful.

This has not been compiled, but shows you what a possible generic implementation of in-order traversal would look like, and how you may accomplish printing each node using operator <<:

class WordTree
{
//...
public:
    // generic, templated inorder traversal function
    template <typename fn>
    void InOrder(WordNode *cur, fn predicate)
    {
       if ( !cur )
          return;
       InOrder(cur->m_left, predicate);

       // call the user-defined function
       predicate(cur);

       InOrder(cur->m_right, predicate);
    }

    friend std::ostream& operator<<(std::ostream &out, const WordTree& rhs);
    //...
};

Now here is the implementation of the operator << and the user-defined function that will be used in WordTree::InOrder:

    // A helper functor to print one node
    struct NodePrinter
    {
      std::ostream* strm;

      // Initialize object with pointer to the stream
      NodePrinter(std::ostream* s) : strm(s) {}

      // function that is called by InOrder
      void operator()(WordNode *cur)
      {
         *strm << cur->m_data << " " << cur->m_count << "\n";
      }
   };

   std::ostream& operator<<(std::ostream &out, const WordTree& rhs)
   {
     // create instance of the functor 
     NodePrinter np(&out);
    // call the InOrder function (assume that get_root() returns the pointer to the root node)
     rhs.InOrder(rhs.get_root(), np);
     return out;
   }

Basically we've made InOrder a generic function. The processing of the node that's visited is done by a user-defined function, function object, or even a lambda would (should) work (in this case, it is the NodePrinter function object). This makes the in-order traversal much more flexible.

For example, if you wanted to concatenate each value in the node (assuming that the data portion is a string), and also get a total count:

std::string allNodes;
int count = 0;
//...
rhs.InOrder(rhs.get_root(), [&](WordNode *cur) { allNodes += cur->m_data; count += cur->m_count });
//..
std::cout << allNodes << "\n" << count;

The above is a lambda function that will be invoked whenever a node is encountered in the traversal.

Upvotes: 0

R Sahu
R Sahu

Reputation: 206637

Instead of

ostream& operator<<(ostream &out, const WordTree& rhs)
{
    out << InOrder(&out, rhs.root);
    return out;
}

use

ostream& operator<<(ostream &out, const WordTree& rhs)
{
    // Invoke InOrder on the WordTree object.
    // Use just out, not &out.
    return rhs.InOrder(out, rhs.root);
}

Update, in response to OP's comment

It's unfortunate that InOrder is not a const member function. It should have been one.

One way to overcome the problem is to create a temporary object and use it.

ostream& operator<<(ostream &out, const WordTree& rhs)
{
    // Invoke InOrder on the WordTree object.
    // Use just out, not &out.
    WordTree temp(rhs);
    return temp.InOrder(out, temp.root);
}

Upvotes: 2

Related Questions