468,513 Members | 1,763 Online

# 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){
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