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 << " ";
}