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.
I've done a similar project like this. The hardest part
of this is the syntax errors from the c++ templates.
I know what these teachers are like .
They will purposly make the project use templates inorder to mess up the student. My bet is that the professor is
even making the students write the template code in
seperate files in order to make it even *more* difficult. This version should compile. Only compile the main file, everything else is included in.
I didn't really fix anything so the infix on your buildTree
will still crash.
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<E>;
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<char> *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()
{
traverseInOrder(root);
}
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 << " ";
}
template <class E> BinaryTree<E>* BinaryTree<E>::buildTree(char *infix, int pos){
BinaryTree<E> *root;
char next;
int len = strlen(infix);
for(; pos < len; pos++){
next = infix[pos];
if (next == '(')
root->root->left = buildTree(infix, ++pos)->root;
else{
root->root->left = (new BinaryTree<E>)->root;
root->root->left->data = (next - 48);
}
pos++;
next = infix[pos];
if (next == '(')
root->root->right = buildTree(infix, ++pos)->root;
else{
root->root->right = (new BinaryTree<E>)->root;
root->root->right->data = (next - 48);
}
}
return root;
}
//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
static BinaryTree* buildTree(char* infix, int pos);
void traverseInOrder();
private:
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
#include <iostream>
#include <cctype>
#include <string>
#include "binary_tree.h"
using namespace std;
int main(){
BinaryTree<char>* mytree;
char dummy, yesOrNo;
const int MAX_STR = 1000;
char infix[MAX_STR];
do{
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 = BinaryTree<char>::buildTree(infix, 0);
//traversePostOrder();
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');
mytree->traverseInOrder();
return 0;
}