LinkBack URL
About LinkBacks
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 << " "; }
