I've done a similar project like this. The hardest partThat'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.
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; }
