Thread: Trying to overload << in a templated Binary Tree

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    33

    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
    Last edited by chinesepirate; 11-23-2008 at 11:28 AM.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
    template <typename T>
    ostream& operator<< (ostream&, const BinaryTree<T>&);
    should work.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Sep 2008
    Posts
    33
    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

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Sep 2008
    Posts
    33
    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

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    So what is the ACTUAL (complete) code?

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

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Registered User
    Join Date
    Sep 2008
    Posts
    33
    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;
    }

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    bn is a pointer, so:
    Code:
    cout << bn;
    prints an address. As mentioned earlier, you should write:
    Code:
    cout << *bn;
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Sep 2008
    Posts
    33
    ^^

    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

  10. #10
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    You never create a valid root node:

    Code:
    BinaryTree<int> *bn = NULL;

  11. #11
    Registered User
    Join Date
    Sep 2008
    Posts
    33
    Its created in the insert function

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Registered User
    Join Date
    Sep 2008
    Posts
    33
    Hey thanks, that worked

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

  15. #15
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Quote Originally Posted by chinesepirate View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM