473,241 Members | 1,534 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,241 software developers and data experts.

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 14578
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

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

Similar topics

1
by: Jerry Khoo | last post by:
hello, everybody, i am kinda new here, nice to meet u all. Now, i am > cs students and are now facing difficult problems in understanding > what a binary tree is, how it works, and the algorithm...
8
by: Jerry Khoo | last post by:
hello, everybody, i am kinda new here, nice to meet u all. Now, i am cs students and are now facing difficult problems in understanding what a binary tree is, how it works, and the algorithm to...
11
by: jova | last post by:
Is there a difference between a Binary Tree and a Binary Search Tree? If so can someone please explain. Thank You.
4
by: Tarique Jawed | last post by:
Alright I needed some help regarding a removal of a binary search tree. Yes its for a class, and yes I have tried working on it on my own, so no patronizing please. I have most of the code working,...
5
by: pembed2003 | last post by:
Hi, I have a question about how to walk a binary tree. Suppose that I have this binary tree: 8 / \ 5 16 / \ / \ 3 7 9 22 / \ / \ / \
3
by: Peter | last post by:
Hi, I have a Class-Tree based on "Command-Pattern" eg. public class Calculator { .... } public abstract class command
22
by: jamestuck21 | last post by:
Hi, I'm trying to work out a binary division problem 1100 / 101010101010111 Here is what I have so far but I'm not sure if I'm doing it correctly and I'm suppose to continue the division...
1
by: hn.ft.pris | last post by:
I have the following code: Tree.h defines a simple binary search tree node structure ########## FILE Tree.h ################ #ifndef TREE_H #define TREE_H //using namespace std; template...
7
by: Vinodh | last post by:
Started reading about Binary Trees and got the following questions in mind. Please help. Definition of a Binary Tree from "Data Structures using C and C++ by Tanenbaum" goes like this, "A...
0
by: jianzs | last post by:
Introduction Cloud-native applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.