![]() |
| | #1 |
| Registered User Join Date: Oct 2002
Posts: 155
| Templated Binary Tree... dear god... 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 << " ";
}
|
| Nakeerb is offline | |
| | #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. |
| Nakeerb is offline | |
| | #3 |
| Programming Sex-God 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? |
| Polymorphic OOP is offline | |
| | #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 |
| Nakeerb is offline | |
| | #5 |
| Registered User 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* |
| Cela is offline | |
| | #6 |
| Programming Sex-God 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. |
| Polymorphic OOP is offline | |
| | #7 |
| Registered User Join Date: Oct 2002
Posts: 155
| I understand. Thank you very much, both of you |
| Nakeerb is offline | |
| | #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;
|
| Nakeerb is offline | |
| | #9 |
| Registered User 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* |
| Cela is offline | |
| | #10 |
| Registered User Join Date: Oct 2002
Posts: 155
| BinaryTree<char>*mytree; ? This just creates an immense list of problems! |
| Nakeerb is offline | |
| | #11 |
| Registered User 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* |
| Cela is offline | |
| | #12 |
| Registered User Join Date: Oct 2002
Posts: 155
| Urgghg, this is never going to get done |
| Nakeerb is offline | |
| | #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. |
| Nick is offline | |
| | #14 | |
| Programming Sex-God Join Date: Nov 2002
Posts: 1,078
| Quote:
| |
| Polymorphic OOP is offline | |
| | #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 |
| Nakeerb is offline | |
![]() |
| Thread Tools | |
| Display Modes | |
|
Similar Threads | ||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| binary interface to binary search tree giving me SUCH A HEADACHE!! | tms43 | C++ Programming | 0 | 11-04-2006 11:07 AM |
| Binary Search Trees Part III | Prelude | A Brief History of Cprogramming.com | 16 | 10-02-2004 03:00 PM |
| Tutorial review | Prelude | A Brief History of Cprogramming.com | 11 | 03-22-2004 09:40 PM |
| Request for comments | Prelude | A Brief History of Cprogramming.com | 15 | 01-02-2004 10:33 AM |
| BST/Red and Black Tree | ghettoman | C++ Programming | 0 | 10-24-2001 10:45 PM |