Binary Tree Calculator

[aemado]

I am writing a program that will evaluate expressions using binary trees. Most of the code has been provided, I just have to write the code for the class functions as listed in the header file. However, I am really new to recursion and trees...and this program uses public functions and private helper functions, which I am completely lost in. Here is the header file:

struct CTNode
{
    NodeType type;
    int operand;
    CTNode *left, *right;
};
 
class CalcTree
{
public:
    CalcTree(); //default constructor
    CalcTree( CalcTree& otherTree ); //copy constructor
    ~CalcTree(); //destructor
 
    void setRoot( NodeType type_, int operand_ );
    //construct a node with the given characteristics and place it at the root of this tree
 
    void setLeft( CalcTree& otherTree );
    //place a copy of the parameter tree as the left subtree of this tree
 
    void setRight( CalcTree& otherTree );
    //place a copy of the parameter tree as the right subtree of this tree
 
    void printIN( ); 
    //member function to print the stored expression in this tree using INFIX notation
 
    void printPOST( );
    //member function to print the stored expression in this tree using POSTFIX notation
 
    float evaluate( );
    //member function to evaluate the stored expression and return an answer
    //assumes that the expression tree is well-formed
    //the client must make sure the expression tree is well fromed before calling this function
 
private:
    CTNode *copyHelper( CTNode *thatroot ); //recursive helper for copy constructor and "set" functions
    //constructs an exact copy of the tree rooted at "thatroot" and returns a pointer to it
 
    void destHelper( CTNode *thisroot ); //recursive helper for destructor
    //completely deallocates all dynamic memory in the tree rooted at "thisroot"
 
    void printINhelper( CTNode *thisroot ); //recursive helper for INFIX printing
    //prints the expression tree rooted at "thisroot" in INFIX order
 
    void printPOSThelper( CTNode *thisroot ); //recursive helper for POSTFIX printing
    //prints the expression tree rooted at "thisroot" in POSTFIX order
 
    float evalHelper( CTNode *thisroot ); //recursive helper for expression evaluation
    //evaluates the expression tree rooted at "thisroot" and returns the answer
    //returns a float so that integer division is avoided
 
    CTNode *root; //pointer to the root node of this expression tree
};
 
#endif
 

If I am not mistaken, the public functions are quite simple, and primarily call the helper functions to do the work, right? I am just kind of lost with the helper functions and the whole concept of recursion. Here are some the functions I already have:

CalcTree::destHelper(CTNode *thisroot){
 
if(root==NULL) return;
 
//if the current root has any subtrees, we must delete them first to prevent memory leak
if(( root->left != NULL ) || ( root->right != NULL ))
    {     
    if( root->left != NULL ) //if there is a left subtree
        {destHelper(root->left); //recursively deallocate it
         root->left=NULL;} //set its pointer to NULL
    if( root->right != NULL ) //if there is a right subtree
        {destHelper(root->right); //recursively deallocate it
         root->right=NULL;} //set its pointer to NULL
    }
 
//at this point we are sure this root has no subtrees so we can delete it    
delete root; 
}
 

CalcTree::printINhelper(CTNode *thisroot){
    //prints the expression tree rooted at "thisroot" in INFIX order
    if ( thisroot != NULL ) {  // Otherwise, there's nothing to print
        printINhelper( thisroot->left );    // Print items in left subtree.
        cout << thisroot->operand << " ";     // Print the root item.
        printINhelper( thisroot->right );   // Print items in right subtree.
    }
 
}
 

Am I even doing this right? I am so lost. Any help or guidance would be greatly appreciated!

[oramified]

I am writing a program that will evaluate expressions using binary trees. Most of the code has been provided, I just have to write the code for the class functions as listed in the header file. However, I am really new to recursion and trees...and this program uses public functions and private helper functions, which I am completely lost in.

I hear ya.

I was searching online for some help with (my guess is) the same exact problem. I can help you as far as my broken code can help you. I notice that you just modified the example code, but that won't work because of the CTNode struct in this class. My code doesn't work yet either, but I may be able to point you in the right direction. For example: here is my printINhelper...

void CalcTree::printINhelper(CTNode *thisroot){
    if(thisroot!=NULL)
    {
        cout<<"(";
        if(thisroot->left!=NULL){
            printINhelper(thisroot->left);
        } 
        if(thisroot->type != OPR){
            if(thisroot->type == ADD) cout<<"+";
            if(thisroot->type == SUB) cout<<"-";
            if(thisroot->type == MUT) cout<<"*";
            if(thisroot->type == DIV) cout<<"/";
        } else cout<<thisroot->operand;
        if(thisroot->right!=NULL) {
            printINhelper(thisroot->right);
        }
        cout<<")";
    }     
}
 

I am fully aware that it's wrong, but I did notice that you didn't compensate for the NodeType type aspect of the struct.

Like I said, I can't get it working either, so if you figure something out, let me know. I'm in section 401 with Neil, you?

[aemado]

I finally figured out the whole recursive helper concept late last night...and finished everything with Neil during his office hours today. I'm just getting started on my intermediate drivers, but if you need any help with the program, just let me know :)