468,513 Members | 1,763 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,513 developers. It's quick & easy.

Binary Tree Calculator

17
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:

Expand|Select|Wrap|Line Numbers
  1. struct CTNode
  2. {
  3.     NodeType type;
  4.     int operand;
  5.     CTNode *left, *right;
  6. };
  7.  
  8. class CalcTree
  9. {
  10. public:
  11.     CalcTree(); //default constructor
  12.     CalcTree( CalcTree& otherTree ); //copy constructor
  13.     ~CalcTree(); //destructor
  14.  
  15.     void setRoot( NodeType type_, int operand_ );
  16.     //construct a node with the given characteristics and place it at the root of this tree
  17.  
  18.     void setLeft( CalcTree& otherTree );
  19.     //place a copy of the parameter tree as the left subtree of this tree
  20.  
  21.     void setRight( CalcTree& otherTree );
  22.     //place a copy of the parameter tree as the right subtree of this tree
  23.  
  24.     void printIN( ); 
  25.     //member function to print the stored expression in this tree using INFIX notation
  26.  
  27.     void printPOST( );
  28.     //member function to print the stored expression in this tree using POSTFIX notation
  29.  
  30.     float evaluate( );
  31.     //member function to evaluate the stored expression and return an answer
  32.     //assumes that the expression tree is well-formed
  33.     //the client must make sure the expression tree is well fromed before calling this function
  34.  
  35. private:
  36.     CTNode *copyHelper( CTNode *thatroot ); //recursive helper for copy constructor and "set" functions
  37.     //constructs an exact copy of the tree rooted at "thatroot" and returns a pointer to it
  38.  
  39.     void destHelper( CTNode *thisroot ); //recursive helper for destructor
  40.     //completely deallocates all dynamic memory in the tree rooted at "thisroot"
  41.  
  42.     void printINhelper( CTNode *thisroot ); //recursive helper for INFIX printing
  43.     //prints the expression tree rooted at "thisroot" in INFIX order
  44.  
  45.     void printPOSThelper( CTNode *thisroot ); //recursive helper for POSTFIX printing
  46.     //prints the expression tree rooted at "thisroot" in POSTFIX order
  47.  
  48.     float evalHelper( CTNode *thisroot ); //recursive helper for expression evaluation
  49.     //evaluates the expression tree rooted at "thisroot" and returns the answer
  50.     //returns a float so that integer division is avoided
  51.  
  52.     CTNode *root; //pointer to the root node of this expression tree
  53. };
  54.  
  55. #endif
  56.  
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:

Expand|Select|Wrap|Line Numbers
  1. CalcTree::destHelper(CTNode *thisroot){
  2.  
  3. if(root==NULL) return;
  4.  
  5. //if the current root has any subtrees, we must delete them first to prevent memory leak
  6. if(( root->left != NULL ) || ( root->right != NULL ))
  7.     {     
  8.     if( root->left != NULL ) //if there is a left subtree
  9.         {destHelper(root->left); //recursively deallocate it
  10.          root->left=NULL;} //set its pointer to NULL
  11.     if( root->right != NULL ) //if there is a right subtree
  12.         {destHelper(root->right); //recursively deallocate it
  13.          root->right=NULL;} //set its pointer to NULL
  14.     }
  15.  
  16. //at this point we are sure this root has no subtrees so we can delete it    
  17. delete root; 
  18. }
  19.  
Expand|Select|Wrap|Line Numbers
  1. CalcTree::printINhelper(CTNode *thisroot){
  2.     //prints the expression tree rooted at "thisroot" in INFIX order
  3.     if ( thisroot != NULL ) {  // Otherwise, there's nothing to print
  4.         printINhelper( thisroot->left );    // Print items in left subtree.
  5.         cout << thisroot->operand << " ";     // Print the root item.
  6.         printINhelper( thisroot->right );   // Print items in right subtree.
  7.     }
  8.  
  9. }
  10.  
Am I even doing this right? I am so lost. Any help or guidance would be greatly appreciated!
Dec 3 '07 #1
2 12857
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...

Expand|Select|Wrap|Line Numbers
  1. void CalcTree::printINhelper(CTNode *thisroot){
  2.     if(thisroot!=NULL)
  3.     {
  4.         cout<<"(";
  5.         if(thisroot->left!=NULL){
  6.             printINhelper(thisroot->left);
  7.         } 
  8.         if(thisroot->type != OPR){
  9.             if(thisroot->type == ADD) cout<<"+";
  10.             if(thisroot->type == SUB) cout<<"-";
  11.             if(thisroot->type == MUT) cout<<"*";
  12.             if(thisroot->type == DIV) cout<<"/";
  13.         } else cout<<thisroot->operand;
  14.         if(thisroot->right!=NULL) {
  15.             printINhelper(thisroot->right);
  16.         }
  17.         cout<<")";
  18.     }     
  19. }
  20.  
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?
Dec 4 '07 #2
aemado
17
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 :)
Dec 5 '07 #3

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

1 post views Thread by Jerry Khoo | last post: by
8 posts views Thread by Jerry Khoo | last post: by
11 posts views Thread by jova | last post: by
4 posts views Thread by Tarique Jawed | last post: by
5 posts views Thread by pembed2003 | last post: by
22 posts views Thread by jamestuck21 | last post: by
7 posts views Thread by Vinodh | last post: by
reply views Thread by NPC403 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.