Thread: Templated Binary Tree... dear god...

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    155

    Templated Binary Tree... dear god...

    This is for a school assignment, first of all. I have shown this to my teacher and even she cannot help me, for she can't figure it out. But if you compile this, it has but one error... the source can't be found either. The purpose of this project is to create a binary tree that accepts an infix string (like, (3 + 4 - 5 * 3) for instance ) and then allows you to output in prefix, postfix, or even infix format again depending on what order you visit the left/right children and the root.

    I really don't expect much help on this one... there's quite a bit of code.

    I also don't know how to get my destructor to work.

    Any help given would be GREATLY appreciated. Our school is having some troubles right now with class-time and the amount of projects due. It would be a great relief to get some help on this one.



    DRIVER FILE:
    Code:
    #include <iostream>
    #include <conio>
    #include <ctype>
    #include <string>
    #include "binary_tree.h"
    using namespace std;
    
    template <class E> BinaryTree<E>* buildTree(char *infix, int pos);
    	
    int main(){
    	BinaryTree<char> mytree;
    	char dummy, yesOrNo;
    	char *infix;
    	
    	do{
    		clrscr();
    		infix[0] = '\0';
    		cout << "Infix Program (Binary Trees)\n\n";
    		cout << "Give me a string in infix form <example: (4 + (4 * 5) / 6) ^ 2)>\r\n";
    		cout << "\nInfix Expression: "; 
    		cin >> dummy >> infix;
    		
    		mytree = buildTree(infix, 0);
    		
    		//traversePostOrder();
    		
    		getch();
    	
    		cout << "\nWould you like to evaluate more expressions (Y or N): ";
    		
    		do{
    			cin >> yesOrNo;
    		}while ((tolower(yesOrNo) != 'y') && (tolower(yesOrNo) != 'n'));
    		
    	}while (tolower(yesOrNo) == 'y');
    
    	return 0;
    }
    
    
    template <class E> BinaryTree<E>* buildTree(char *infix, int pos){
    	BinaryTree *root;
    	char next;
    	
    	for(pos; pos < strlen(infix) - 1; pos++){
    		next = infix[i];
    		
    			if (next == '(')
    				root -> left = buildTree(infix, ++pos);
    			
    			else{
    				root -> left = new BinaryTree;	  
    				root -> left -> data = (next - 48);
    			}
    			
    			pos++;
    			next = infix[i];
    			
    			 if (next == '(')
    			 	root -> right = buildTree(infix, ++pos);
    			
    			 else{
    			 	root -> right = new BinaryTree;
    				root -> right -> data = (next - 48);
    			} 
    			
    	}
    	
    	return root;
    }











    HEADER FILE:
    Code:
    //Binary Tree header file.
    
    
    #ifndef BINARY_TREE_H
    #define BINARY_TREE_H
    
    
    template <class E> struct node{
        E data;       //data unit of any given datatype
        node<E> *left;   //pointer to a "lesser-than" child             
        node<E> *right;  //pointer to a "greater-than" child          
    };
    
    
    template <class E> class BinaryTree{
    
    	public:             
        	BinaryTree();       //default constructor, sets root to NULL
    		~BinaryTree();      //default destructor (memory leaks are bad)                   
          
    		bool isEmpty(const node<E> *&root); 
    		bool insert(node<E> *&root, const E &data);        //insert a node into the tree
            bool remove(node<E> *&root, const E &data);     //checks if a node can be deleted
    		
    		
    		
    		void traverseInOrder(node<E> *root);
    		void traversePreOrder(node<E> *root);
    		void traversePostOrder(node<E> *root);
                              
    	private:
        	node<E> *root;              //the root of the tree      
    };
    
    	
    
    #include "binary_tree.cpp"
    #endif











    IMPLEMENTATION FILE:
    Code:
    //Binary Tree implementation
    
    template <class E> BinaryTree<E>::BinaryTree(){
    	root = NULL;
    }
    
    
    template <class E> BinaryTree<E>::~BinaryTree(){   
    	//delete node<E>;
    } 
    
    template <class E> bool BinaryTree<E>::isEmpty(const node<E> *&root){
    	
    	if (!root)
    		return true;
    		
    	else
    		return false;
    }
    
    
    template <class E> bool BinaryTree<E>::insert(node<E> *&root, const E &data){
    	
    	if (!root){
    		node<E> *temp = new node;
    		
    		if (!temp)               //memory couldn't be allocated, node can't be inserted
    			return false;
    			
    		temp -> data = data;
    		temp -> left = NULL;
    		temp -> right = NULL;
    		root = temp;
    		return true;             //successful
    	}
    	
    	if (data <= root -> data)
    		return insert(root -> left, data);         //recurse to the left
    	
    	else if (data > root -> data)
    		return insert(root -> right, data);        //recurse to the right
    	
    }
    
    
    template <class E> bool BinaryTree<E>::remove(node<E> *&root, const E &data){
    	
    	if (!root)                 //base case, tree is empty
    		return false;
    	
    	if (data == root -> data){      //found node to be removed
    		node *oldroot = root;       //first save-root, points to removal-node
    		//Case 1 - one or no children
    		
    		if (root -> left == NULL)          //no left child
    			root = root -> right;
    		
    		else if (root -> right == NULL)    //no right child
    			root = root -> left;
    			
    		if (oldroot != root){		//if one of the above is true
    			delete oldroot;
    			return true;	
    		}  //root is reassigned, node to be removed is deleted
    		
    		node<E>* parent = root;
    		node<E>* next = root -> right;
    		
    		while (next -> left){	//navigate right to smallest
    			parent = next;
    			next = next -> left;
    		}
    		
    		if (parent == root)		//unlink this node from the tree
    			root -> right = next -> right;
    			
    		else
    			parent -> left = next -> right;
    			
    		next -> left = root -> left;   //Make this element the new root	
    		next -> right = root -> right;
    		delete root;
    		root = next;
    		return true;   
    	}	 
    	
    	else if (data <= root -> data);
    		return remove(root -> left, data);
    	
    	else if (data > root -> data)
    		return remove(root -> right, data);
    	
    }
    
    
    template <class E> void BinaryTree<E>::traverseInOrder(node<E> *root){
    	
    	if (!root)		//test first to see if done
    		return;
    		
    	traverseInOrder(root -> left);
    	cout << root -> data << " ";	
    	traverseInOrder(root -> right);	   
    }
    
    
    template <class E> void BinaryTree<E>::traversePreOrder(node<E> *root){
    	
    	if (!root)		//test first to see if done
    		return;
    		
    	cout << root -> data << " ";		
    	traversePreOrder(root -> left);
    	traversePreOrder(root -> right);	
    }
    
    
    template <class E> void BinaryTree<E>::traversePostOrder(node<E> *root){
    	
    	if (!root)		//test first to see if done
    		return;
    		
    	traversePostOrder(root -> left);
    	traversePostOrder(root -> right);
    	cout << root -> data << " ";	
    }

  2. #2
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    I am terribly sorry for that huge post. I don't know how else I can get help on this; this is my last resort and I have no clue how this project is going to work out.

  3. #3
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    #including the cpp is completely uneccissary if it is in the the same project as your other files. It should work without it.

    What is the other error you're getting?

  4. #4
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    Line 23: Could not find a match for 'buildTree<E>(char *, int)' in function main()

    --This if when you run the driver file.


    Polymorphic OOP: I am aware of this, but this is the format the teacher requires it.

    Anyways, I really do think it has something to do with the templates. However, when I convert these back to chars instead of the currently-unknown datatype "E" I get a plethora of errors. I just have no idea where I went wrong

  5. #5
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    >>template <class E> BinaryTree<E>* buildTree(char *infix, int pos);
    This is your declaration.

    >>mytree = buildTree(infix, 0);
    This is how you call it. Now tell me, how does buildTree know what kind of BinaryTree to return? It doesn't, you have to tell it.

    mytree = buildTree<char>(infix, 0);
    *Cela*

  6. #6
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    #including cpp's is usually considered poor practice.

    You've got quite a few problems with your code. You can't just refer to the Binary Tree type just as BinaryTree because it is templated. You have to say which version of the binary tree you want IE BinaryTree<int>, etc. For instance, in your BuildTree function (which really should be redesigned and would be better off as a member function) does it improperly -- the first line should be BinaryTree< E > *root

    Also, when you called your BuildTree function you didn't specify which "version" you wanted.

    I'm not at a compiler right now, but those are the big problems that really stand out. You might want to study up on templates because that's where you're most of your mistakes.

  7. #7
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    I understand. Thank you very much, both of you

  8. #8
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    Code:
    template <class E> BinaryTree<E>* buildTree(char *infix, int pos);
    	
    int main(){
    	BinaryTree<char> mytree;
    	char dummy, yesOrNo;
    	char *infix;
    	
    	do{
    		clrscr();
    		infix[0] = '\0';
    		cout << "Infix Program (Binary Trees)\n\n";
    		cout << "Give me a string in infix form <example: (4 + (4 * 5) / 6) ^ 2)>\r\n";
    		cout << "\nInfix Expression: "; 
    		cin >> dummy >> infix;
    		
    		mytree = buildTree<char>(infix, 0);
    		
    		//traversePostOrder();
    		
    		getch();
    	
    		cout << "\nWould you like to evaluate more expressions (Y or N): ";
    		
    		do{
    			cin >> yesOrNo;
    		}while ((tolower(yesOrNo) != 'y') && (tolower(yesOrNo) != 'n'));
    		
    	}while (tolower(yesOrNo) == 'y');
    
    	return 0;
    }
    
    
    template <class E> BinaryTree<E>* buildTree(char *infix, int pos){
    	BinaryTree<E> *root;
    Sorry again... but even after the changes you both suggested I have the error, on the same line, of "Cannot convert ' BinaryTree<char> *' to 'BinaryTree<char>'"

  9. #9
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    >>BinaryTree<char> mytree;
    You might want to start reading your error messages, it says that the above code doesn't declare a pointer, make it so and the error will go away. Since buildTree returns a pointer, it makes no sense to assign that return value to a nonpointer, right?
    *Cela*

  10. #10
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    BinaryTree<char>*mytree; ?

    This just creates an immense list of problems!

  11. #11
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    >>This just creates an immense list of problems!
    Then you should delete everything you've done and start smaller next time. You're confusing the compiler by telling it you'll do something and then later doing something else.
    *Cela*

  12. #12
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    Urgghg, this is never going to get done

  13. #13
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Even if you did get the template situation done you still
    have problems infix is never allocated. You should always
    code everything without templates then add the templates
    in after testing the code.

    In order to build a tree from an infix expression it is almost
    always necessary to use a stack so your build tree method
    is wrong. Well really wrong it doesn't even consider +, - etc.
    You also should make build tree private or add
    a combine tree method to your tree class.

  14. #14
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    Originally posted by Nick
    You should always code everything without templates then add the templates in after testing the code.
    That's really not necissary. It's a waste of time for no reason. He might want to do it for his first couple classes if he's really not sure about templates, but other than that there's no problems in just making things templated from the start and it's just as easy.

  15. #15
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    I am not concerned with the programming style right now. I just want it working. Right now it's probably something simple I am missing

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