Trying to overload << in a templated Binary Tree

So that if I have a binary tree:

Code:

---

BinaryTree<int> *t = new BinaryTree<int>(5);

---

And there have been more numbers inserted I can just say:

Code:

---

cout << bn;

---

I have overloaded this operator before, but never with templates, so I am unsure where I should start.

Here is my BinaryTree class:

Code:

---

template <class T>
class BinaryTree{
        public:
                BinaryTree(T); //constructor
                BinaryTree<T>* insert(T, BinaryTree<T>*);
                void inorder(BinaryTree<T>*); //prints using inorder traversal
                int countNodes(BinaryTree<T>*);
        private:
                T data;
                BinaryTree* left;
                BinaryTree* right;
};

---

I believe the function should be something like this:

Code:

---

friend ostream& operator<< <>(ostream&, const BinaryTree<T>&)

---

I know you can't put << or >> overloaded functions as a member function, so does this not require a prototype, or just put it outside of the class and above the implementation?

Hope this makes sense, thanks.

*EDIT* Actually, I am supposed to make it a friend function, so I would put it in the class

Code:

---

template <typename T>
ostream& operator<< (ostream&, const BinaryTree<T>&);

---

should work.

--
Mats

If i do this:

Code:

---

template <class T>
ostream& operator<< (ostream& out, const BinaryTree<T>& bt){
        out << bt.data;
        return out;
}

---

cout << t; just prints a memory address

is t a tree, or a pointer to tree. If the latter, you either need a function that takes a tree pointer, or use *t to print the actual tree.

--
Mats

Yes its a pointer, I tried this as well:

Code:

---

friend ostream& operator<<(ostream&, const BinaryTree<T>*);

---

And implementation:

Code:

---

template <class T>
ostream& operator<<(ostream& out, const BinaryTree<T>* bt){
        out << bt->data;
        return out;
}

---

But that gives me some fatal error

So what is the ACTUAL (complete) code?

I suspect you haven't actually got a valid pointer to data.

--
Mats

binarytree.cpp

Code:

---

#include <iostream>
using namespace std;

template <class T>
class BinaryTree{
        public:
                BinaryTree(T);
                BinaryTree<T>* insert(T, BinaryTree<T>*);
                void inorder();
                int countNodes(BinaryTree<T>*);
                BinaryTree<T>* reverse(BinaryTree<T>*);
                friend ostream& operator<<(ostream&, const BinaryTree<T>*);
        private:
                T data;               
                BinaryTree* left;
                BinaryTree* right;
};

template <class T>
BinaryTree<T>::BinaryTree(T x){
        data=x;
        left=NULL;
        right=NULL;
}

template <class T>
BinaryTree<T>* BinaryTree<T>::insert(T x, BinaryTree<T>* bt ){
        if( bt == NULL ){
                bt = new BinaryTree<T>(x);
    }
    else if( x < bt->data ){
        bt->left = insert( x, bt->left );
    }
    else if( x > bt->data ){
        bt->right = insert( x, bt->right );
    }
    return bt;
}

template <class T>
void BinaryTree<T>::inorder(){
    if(this!=NULL){
        this->left->inorder();
        cout << this->data << endl;
        this->right->inorder();
  }
}

template <class T>
int BinaryTree<T>::countNodes(BinaryTree<T>* bt) {
        if ( bt == NULL ) return 0;
    else {
                int count = 1;
        count += countNodes(bt->left);
        count += countNodes(bt->right);
        return count;
    }
}

template <class T>
BinaryTree<T>* BinaryTree<T>::reverse(BinaryTree<T>* bt){
        if(bt!=NULL){
                BinaryTree<T>* temp = bt->left;
                bt->left=bt->right;
                bt->right=temp;
        }
        return bt;
}


template <class T>
ostream& operator<<(ostream& out, const BinaryTree<T>* bt){
        out << bt->data;
        return out;
}

---

main.cpp

Code:

---

#include <iostream>
#include "binarytree.cpp"
using namespace std;

int main(){
        int choice;
        int size;
        bool play=true;
        BinaryTree<int> *bn = NULL;
        while(play){
                cout << "Menu Display" << endl << "-------------" << endl << "1) Enter Data" << endl << "2) Print Tree" << endl
                        << "3) Reverse Tree" << endl << "4) Quit" << endl;
                cout << "Enter your choice: ";
                cin >> choice;
                if(choice==1){
                        int num;
                        cout << "Enter data for tree: ";
                        cin >> num;
                        bn = bn->insert(num,bn);
                }
                if(choice==2){
                        size=bn->countNodes(bn);
                        cout << "Tree size = " << size << endl << "-------------" << endl;
                        cout << bn;
                }
                if(choice==3){
                        bn = bn->reverse(bn);
                }
                if(choice==4){
                        play=false;
                }
        }

        system("PAUSE");
        return 0;
}

---

bn is a pointer, so:

Code:

---

cout << bn;

---

prints an address. As mentioned earlier, you should write:

Code:

---

cout << *bn;

---

^^

error C2679: binary '<<' : no operator found which takes a right-hand operand of type 'BinaryTree<T>' (or there is no acceptable conversion)

Which doesn't make sense because I don't see anywhere with just BinaryTree<T>, it is all BinaryTree<T>* I think

You never create a valid root node:

Code:

---

BinaryTree<int> *bn = NULL;

---

Its created in the insert function

After I fix the warning about the friend function template like this:

Code:

---

    template <typename X>
    friend ostream& operator<<(ostream&, const BinaryTree<X>*);

---

it works for me:

Code:

---

E:\Temp>g++ -Wall main.cpp

E:\Temp>a
Menu Display
-------------
1) Enter Data
2) Print Tree
3) Reverse Tree
4) Quit
Enter your choice: 1
Enter data for tree: 2
Menu Display
-------------
1) Enter Data
2) Print Tree
3) Reverse Tree
4) Quit
Enter your choice: 2
Tree size = 1
-------------
2Menu Display
-------------

---

--
Mats

Read this FAQ: Why do I get linker errors when I use template friends?

As described, a fix goes like this:

Code:

---

template<typename T>
class BinaryTree;

template<typename T>
std::ostream& operator<<(std::ostream& out, const BinaryTree<T>& tree);

template<typename T>
class BinaryTree {
public:
    // ...

    friend std::ostream& operator<< <>(std::ostream& out, const BinaryTree<T>& tree);

    // ...

---

Actually, it may be good to separate a BinaryTree from a BinaryTreeNode.

Also, you should rename binarytree.cpp to binarytree.h and get rid of the using directive in it.

Hey thanks, that worked

I didn't know you had to have a separate template for the friend function

Quote:

---

Originally Posted by chinesepirate

Its created in the insert function

---

The only call to insert that I see in your main is

Code:

---

bn = bn->insert(num,bn);

---

But you are dereferencing a null pointer to make the call.

Quote:

---

Originally Posted by Thantos

The only call to insert that I see in your main is

Code:

---

bn = bn->insert(num,bn);

---

But you are dereferencing a null pointer to make the call.

---

But unless the function is virtual AND the table for the object is part of the object itself, it should call the insert function [yes, that's a BAD thing to do, but you can actually get away with it in many compilers - but yes, it's undefined].

As Laserlight points out, you probably should split the tree and the node from each other.

--
Mats