Binary Tree Revisited: Near Completion

With the help of Nick I am coming very close to being able to insert data into this binary tree... yet some parts still refuse to work.

Here is the entire code segment thus far

Code:

---

#include <iostream>
#include <ctype>
#include <conio>
using namespace std;


struct Token {
    char type;
    double val;
};


struct node{
        node();
        char data;
        node *left, *right;
};


node::node(){
        left = NULL;
        right = NULL;
}


void read_next_token(Token &next_token);
node* start(Token &next_token);
node* expr(Token &next_token);
node* term(Token &next_token);
node* factor(Token &next_token);
void traverseInOrder(node *root);


int main(){
    node* val;
        Token next_token;
       
        cout << "Parenthesized Infix equation: ";
       
    read_next_token(next_token); 
    val = start(next_token);     
    cout << "Result = ";
        traverseInOrder(val);
        getch();
    return 0;
}  //end main
       

void read_next_token(Token &next_token){
    double c;

    c = cin.get();    //doesn't require an enter press

    if (isdigit(c)) {
        next_token.type = '#';       
        next_token.val  = c - 48;    //to get rid of the ascii value offset
        return;
    }
       
        next_token.type = char(c); 
} 


node* start(Token &next_token){
    node* val = expr(next_token); 
    return val;                   
}


node* expr(Token &next_token){
    node* val = new node;

    if (val -> left == NULL)
                                  val -> left = term(next_token);
                        else
                                val -> right = term(next_token);
         
       
    switch(next_token.type){
       
            case '+':
                case '-':
                read_next_token(next_token);
                if (val -> left == NULL)
                                  val -> left = expr(next_token);
                        else
                                val -> right = expr(next_token);
                break;
           
                       
       
                       
            default:
                break;
    }
 
    return val;
}


node* term(Token &next_token){
    node* val = new node;
        //zerotest;

        if (val -> left == NULL)
    val -> left = factor(next_token);
        else
        val -> right = factor(next_token);
       
    switch(next_token.type){
       
            case '*':
                case '/':
                read_next_token(next_token);  //get the next inputted letter
                       
                if (val -> left == NULL)
                                  val -> left = term(next_token);
                        else
                                val -> right = term(next_token);
                break;
                       
       
                       
            default:
                break;
    }

    return val;
}
   

node* factor(Token &next_token){
    node* val = new node;
   
    switch(next_token.type){
       
            case '#':                        //if the type of the token is a number
                val -> data = char(next_token.val);     
                read_next_token(next_token);  //get the next inputted letter
                break;
                       
            case '(':            //the only other thing it can be here is a (
                read_next_token(next_token);  //get the next inputted letter
                if (val -> left == NULL)
                                  val -> left = expr(next_token);
                        else
                                val -> right = expr(next_token);
                read_next_token(next_token);  //get the next inputted letter
                break;
                       
            default:
                break;
    }
   
    return val; 
}


void traverseInOrder(node *root){
       
        if (!root)                //test first to see if done
                return;
               
        traverseInOrder(root->left);
        cout << root->data << " ";       
        traverseInOrder(root->right);         
}

---

Nick: Now I understand how this "descended recurse" works. Very spiffy :P Unfortunately I am now having trouble converting this to the node insertions. Anyone able to tell me why I am not able to view the data I desire when I do an inOrder traversal? Perhaps I am not inserting correctly...

Alright there we go. Alignments fixed

Does this have anything to do with checking for left?

In each function you just look at the different cases
that can arise and return a tree representing them.
You only need to use the constructor
node(char data, node* left, node* right). This way
you return a tree even if it has incorrect data.

In most of the functions all you need is
node* root, *right, *left. So for example if your
parsing 5 + 6 in expr you would create a tree for it by
doing
left = term();
right = expr();
root = new node('+', left, right);

Be aware that if your just parsing
4;
your function must basically do
left = term();
root = left;
This will go through the default case in expr and term.

i dint go through your entire program.. but i feel your traversal is wrong... You have to start from the root but display it only after the leaf node is done etc.. fro different taversal...



example

Code:

---

FOR PRE ORDER DISPLAY

tree::predisplay(node *te)
{

cout<<"\n"<<te->key;

if(te->left!=NULL)
predisplay(te->left);

if(te->right!=NULL)
predisplay(te->right);

return SUCCESS;
}


POST ORDER DISPLAY

tree::postdisplay(node *te)
{

if(te->left!=NULL)
postdisplay(te->left);

if(te->right!=NULL)
postdisplay(te->right);

cout<<"\n"<<te->key;

return SUCCESS;
}


INORDER DISPLAY
tree::indisplay(node *te)
{

if(te->left!=NULL)
indisplay(te->left);

cout<<"\n"<<te->key;

if(te->right!=NULL)
indisplay(te->right);



return SUCCESS;
}

---

so all these functions are called with the root as argument.. and what is !root supposed to do...

His traversal is correct. As long as the tree is formed
correctly it should run. But I think passing next_token
into each function is ugly. Better to use a class or use
a global variable.

You should probably skip white space at the beginning of
read_next_token and I'm not sure why you are using double c. Try to test each function in isolation. Simply test read_next_token then test factor, term, expr in that order.

Nakeerb here, temporary name.

Nick, then is all the new code I wrote a waste? I understand how you mean but I have a feeling I'd have to clean up SO much code to get it working. The ( and ) are not supposed to be part of the binary tree at all. only numbers and operators, and all evaluations are FULLY parenthesized.

As in you'll never see (3 + 2 + (4 + 5)), it'd be ((3 + 2)+(4+5))



However, I have too much crappy code written in alerady. What would I do in place of something such as this:

Code:

---

switch(next_token.type){
       
            case '#':                        //if the type of the token is a number
                val -> data = char(next_token.val);     
                read_next_token(next_token);  //get the next inputted letter
                break;
                       
            case '(':            //the only other thing it can be here is a (
                read_next_token(next_token);  //get the next inputted letter
                if (val -> left == NULL) //EQUAL TERMS YOU FOOL
                                  val -> left = expr(next_token);
                        else
                                val -> right = expr(next_token);
                read_next_token(next_token);  //get the next inputted letter
                break;
                       
            default:
                break;
    }

---

If you can help me with this function I will do the rest. I am just totally lost. Do I need to declare two node pointers *val and *root? Or declare root when I... auugh! I couldn't sleep last night because of this stupid binary tree problem O.o;;

when you say left, I assumed you meant a temp node's left is equal. Then you pass the temp node's left into the constructor... oyyy, no idea.

Code:

---

switch(next_token.type){
    case '#':                        //if the type of the token is a number
        val -> data = char(next_token.val);     
        read_next_token(next_token);  //get the next inputted letter
        break;
    case '(':            //the only other thing it can be here is a (
        read_next_token(next_token);  //get the next inputted letter
        if (val -> left == NULL) //EQUAL TERMS YOU FOOL
        val -> left = expr(next_token);
        else
        val -> right = expr(next_token);
        read_next_token(next_token); 
                break;
        default:
                break;
}

---

You could do something like this

Code:

---

node* factor(Token &next_token){
    node* root = NULL;
   
    switch(next_token.type){
    case '#':                       
          root = new node(next_token.val, NULL, NULL);     
          read_next_token(next_token); 
          break;
    case '(':         
          read_next_token(next_token);
          root = expr(next_token);
          read_next_Token(next_token);
    default:
          break;
    }
   
    return root; 
}

---

So I can do this for all functions? When would I need to append to right side or left?

This is just for factor. The functions like expr there
are cases where you would set root = term() (this is
in the default cases) and there
are cases where you would do something like
node* left = term();
node* right = expr();
root = node('+', left, right)

I rewrote another program that does the same based on the psuedocode I was given today at around noon. However it still does not work. I know I am going off on an extreme tangent by posting this, but any help would be appreciated.

Code:

---

#include <iostream>
#include <conio>
#include <ctype>
#include <cstdlib>
using namespace std;

class BinaryTree{
        public:
               
                ~BinaryTree(){
               
                        if (left != NULL)
                                delete left;
                               
                        if (left != NULL)
                                delete right;
                               
                }
               
        BinaryTree *left;    //pointer to a left subtree
        BinaryTree *right;    //pointer to a right subtree
        char data;            //node data
};

BinaryTree* buildTree(char *infix, int &pos);
void preOrderTraverse(BinaryTree *root);
void postOrderTraverse(BinaryTree *root);
double evaluate(BinaryTree *root);
bool isOperator(char ch);
void changecolor(char* word, int color);
void flushin();


int main(){
        char infix[50], yesOrNo;
        BinaryTree *tree;
        int pos = 1;
       
        do{
                clrscr();
                changecolor("Binary Expression Tree\r\n\r\n", LIGHTGREEN);
                cout << "Give me a <fully> parenthesized infix equation: \n";
                changecolor("\r\nInfix Expression: ", WHITE);
                cin.getline(infix, '\n');
                cout << endl << endl;
               
                tree = buildTree(infix, pos);      //inserts infix expression into a binary tree
                cout << "Prefix form of infix: ";
                preOrderTraverse(tree);            //outputs prefix form of infix
                cout << "\nPostfix form of infix: ";
                postOrderTraverse(tree);          //outputs postfix form of infix
               
                cout << "\n\nEvaluation of tree: ";
                evaluate(tree);
               
                delete tree;  //returns the memory to the heap
               
                cout << "\nAgain? ";
               
                do{
                        cin.get(yesOrNo);
                }while((tolower(yesOrNo) != 'y') && (tolower(yesOrNo) != 'n'));
               
                flushin();  //clear input buffer
        }while(tolower(yesOrNo) == 'y');
       
        return 0;
}


BinaryTree* buildTree(char *infix, int &pos){
        BinaryTree *root = new BinaryTree;
       
        if(infix[pos] == '(')
                root -> left = buildTree(infix, ++pos);    //recursive call: builds a subtree to the left
       
        else{
                root -> left = new BinaryTree;
                cout << infix[pos] << " being added to left branch...\n";
                root -> left -> data = infix[pos];        //assigns data unit
        }
       
        pos++;                        //so we are able to get the next character of infix
        root -> data = infix[pos];    //assigns the operator to the root's data character
        pos++;                        //so we are able to get the next character of infix
       
        if (infix[pos] == '(')
                root -> right = buildTree(infix, ++pos);  //recursive call: builds a subtree to the right
       
        else{
                root -> right = new BinaryTree;
                cout << infix[pos] << " being added to right branch...\n";
                root -> right -> data = infix[pos];
        }
       
        pos++;      //skip over the ending ) bracket
        return root;
               
}


void preOrderTraverse(BinaryTree *root){
        cout << (root -> data);                          //output the data of the root
       
        if (root -> left)
                preOrderTraverse(root -> left);  //traverse down to the left side of the tree
               
        if (root -> right)         
                preOrderTraverse(root -> right); //traverse down to the right side of the tree       
}


void postOrderTraverse(BinaryTree *root){       

        if (root -> left)
                postOrderTraverse(root -> left);  //traverse down to the left side of the tree
       
        if (root -> right)                 
                postOrderTraverse(root -> right); //traverse down to the right side of the tree
               
        cout << (root -> data);              //output the data of the root
}


double evaluate(BinaryTree *root){
        double temp, divisor;
       
        if (isdigit(root -> data))      //if the data character is a number
                temp = (root -> data) - 48;  //convert it's ascii value to a format a double can recognize
               
               
        if (isOperator(root -> data)){  //if the data character is an operator
       
                switch (root -> data){  //apply the operator to the left and right values using inorder recursive traversal
                        case '+': temp = evaluate(root -> left) + evaluate(root -> right); break;
                        case '-': temp = evaluate(root -> left) - evaluate(root -> right); break;
                        case '*': temp = evaluate(root -> left) * evaluate(root -> right); break;
                        case '/':
                                divisor = evaluate(root -> right);
                               
                                if (divisor == 0){  //cannot divide by 0
                                        cout << "\nDivide by 0 error.\n";
                                        exit(1);
                                }
                               
                                else
                                        temp = evaluate(root -> left) / divisor;
                                       
                                break;
                               
                        case '^':        temp = pow(evaluate(root -> left), evaluate(root -> right)); break;
                        default: cout << "\nError, operator unknown\n"; break;       
                         
                }
       
        }       
               
        return temp;
}


bool isOperator(char ch){
        string acceptedOperators = "+-*/^";
       
        if(acceptedOperators.find(ch, 0) != string::npos)    //if ch can't be found in the string
                return true;
               
        else
                return false;
               
} //end bool isOperator


void changecolor(char* word, int color){
        textcolor(color);                  //changes text to the color given through the argument
        cprintf("%s", word);                      //outputs the string in the given color
        //cprintf(word);
        textcolor(LIGHTGRAY);        //change color back to the default light gray
} //end void changecolor


void flushin(){

        while (cin.get() != '\n'){}
       
} //end void flushin

---

It took me only about 10 minutes
to add the few lines to build the tree (:

These are the two most important functions to build the
tree the rest of the functions follow the same form.

Code:

---

Node* term()
{
    Node* root, *left, *right;
   
    left = factor();

    switch(next_token.type) {
    case MULTIPLY:
        match(MULTIPLY);
        right = term();
        root = new Node('*', left, right);
        break;
    case DIVIDE:
        match(DIVIDE);
        right = term();
        root = new Node('/', left, right);
        break;
    default:
        root = left;
        break;
    }

    return root;
}
   

Node* factor()
{
    Node* root = 0;
   
    switch(next_token.type) {
    case NUMBER:
        root = new Node('0' + next_token.val, 0, 0);
        match(NUMBER);
        break;
    case LEFT_PARAN:
        match(LEFT_PARAN);
        root = expr();
        match(RIGHT_PARAN);
        break;
    default:
        break;
    }
   
    return root;
}

---

Code:

---


//This is the header file "binary_tree.h"


//===========================/=/=/=/=/=/=/=========================//
//                            STRUCTURES                          //
//===========================/=/=/=/=/=/=/=========================//

#ifndef BINARY_TREE_H
#define BINARY_TREE_H


struct BinaryTree{    //contains the neccessary functions and data for a functioning binary expression tree

        BinaryTree();  //Default constructor
        //Precondition: Object has been declared with no arguments
        //Postcondition: The left and right pointers have been set to NULL
       
        ~BinaryTree();  //Destructor
        //Precondition: The object exists, and has been deleted by "delete"
        //Postcondition: The left and right pointers' memory are sent back to the heap
       
        char data;            //node data (can be either a digit or an operator)
        BinaryTree *left;    //pointer to a left subtree
        BinaryTree *right;    //pointer to a right subtree
};  //end struct BinaryTree


#endif

---

Code:

---


//===========================/=/=/=/=/=/=/=========================//
//                              INCLUDES                          //
//===========================/=/=/=/=/=/=/=========================//


#include <iostream>      //for the insertion operators, cout, and cin
#include <conio>          //for the color functions and clrscr()
#include <ctype>          //for the isdigit() and tolower() functions
#include <cstdlib>        //for the exit() function
#include <cmath>          //for the pow function
#include "binary_tree.h"  //contains the struct for the binary tree
using namespace std;


//===========================/=/=/=/=/=/=/=========================//
//                        FUNCTION PROTOTYPES                      //
//===========================/=/=/=/=/=/=/=========================//


BinaryTree* buildTree(char *infix, int &pos);
//Precondition: infix has been given an infix equation string by the user, and
//pos has been given a value (to begin with, it is 1)
//Postcondition: A binary expression tree is created, returning the root from
//a fully parenthesized expression given through infix. It stores digits under
//left and right nodes, and if a parentheses is encountered, it will branch
//off into a new subtree and populate the node with data. The roots of the subtrees
//are operators, with digits (or a new operator possessing more children) for children.

void preOrderTraverse(BinaryTree *root);
//Precondition: root points to a populated binary expression tree
//Postcondition: Traverses the list recursively and outputs the prefix form of the
//infix expression

void postOrderTraverse(BinaryTree *root);
//Precondition: root points to a populated binary expression tree
//Postcondition: Traverses the list recursively and outputs the postfix
//form of the infix expression

void inOrderTraverse(BinaryTree *root);
//Precondition: root points to a populated binary expression tree
//Postcondition: Traverses the list recursively and outputs the infix
//form of the infix expression, but it will be in order (order of operations will not
//apply here since it's outputted in the order of evaluation).

double evaluate(BinaryTree *root);
//Precondition: root points to a populated binary expression tree
//Postcondition: The solution to the calculation of the data in the binary
//tree is returned recursively

bool isOperator(char ch);
//Precondition: ch has been given a value
//Postcondition: returns true if ch is either +, -, *, /, or ^

void changecolor(char* word, int color);
//precondition: word has been given a string value, and color has been given a number
//postcondition: conio function textcolor() has been called within function changecolor,
//changing the char* word into the color given by the int color.

void flushin();
//Postcondition: input buffer cleared to avoid unwanted input values


//===========================/=/=/=/=/=/=/=========================//
//                          IMPLEMENTATION                        //
//===========================/=/=/=/=/=/=/=========================//


int main(){
        char infix[50], yesOrNo;
        int pos;                //index variable
        BinaryTree *tree;        //our binary tree! Everyone say hi!
       
        do{
       
                clrscr();
                pos = 0;  //to be used as the index variable for infix. 0 is the start of a string
                changecolor("Binary Expression Tree\r\n\r\n", LIGHTGREEN);
                cout << "Give me a <fully> parenthesized infix equation: \n";
                changecolor("\r\nInfix Expression: ", WHITE);
                cin.getline(infix, '\n');
                cout << endl << endl;
               
                tree = buildTree(infix, pos);      //inserts infix expression into a binary tree
                cout << "Prefix form of infix (preorder traversal): \n\t";
                preOrderTraverse(tree); 
                       
                cout << "\n\nPostfix form of infix (postorder traversal): \n\t";
                postOrderTraverse(tree);   
                   
                cout << "\n\nInfix form of infix (inorder traversal, read from left to right): \n\t";
                inOrderTraverse(tree);          //outputs infix form of infix, but from the tree! Amazing!
               
                changecolor("\r\n\r\nEvaluation of tree: ", LIGHTBLUE);
                cout << evaluate(tree);  //outputs the solution to the infix equation from the tree
               
                delete tree;  //returns the memory to the heap
               
                cout << "\n\n\nAgain? ";
               
                do{
                        cin.get(yesOrNo);
                }while((tolower(yesOrNo) != 'y') && (tolower(yesOrNo) != 'n'));  //repeats if user doesn't enter y or n
               
                flushin();  //clear input buffer
        }while(tolower(yesOrNo) == 'y');  //continues the program as long as they say 'y'
       
        return 0;
} //end main


/*struct BinaryTree function definitions*/


BinaryTree::BinaryTree(){ 
        left = NULL;   
        right = NULL;
} //end BinaryTree default constructor


BinaryTree::~BinaryTree(){
               
        if (left != NULL)  //if the pointer is being used
                delete left;    //return it to the heap
                               
        if (left != NULL)  //if the pointer is being used
                delete right;  //return it to the heap
                               
} //end BinaryTree destructor


/*driver file function definitions*/


BinaryTree* buildTree(char *infix, int &pos){
        BinaryTree *temp_root = new BinaryTree;      //allocates memory
       
        pos++; //advance one character (either a ( or a digit)
       
        if (infix[pos] == '(')  //if you encounter a parenthese
                temp_root -> left = buildTree(infix, pos);    //recursive call: creates a subtree to the left
       
        else{
                temp_root -> left = new BinaryTree;            //allocate memory
                temp_root -> left -> data = infix[pos];        //assigns data unit
        }
       
        pos++;                        //so we are able to get the next character of infix
        temp_root -> data = infix[pos];    //assigns the operator to the root's data character
        pos++;                        //so we are able to get the next character of infix
       
        if (infix[pos] == '(')  //if a nested parenthese arises
                temp_root -> right = buildTree(infix, pos);  //recursive call: creates a subtree to the right!
       
        else{       
                temp_root -> right = new BinaryTree;          //allocate memory
                temp_root -> right -> data = infix[pos];      //assigns data unit
        }
       
        pos++;      //skip over the ending ) bracket
        return temp_root;
} //end buildTree()


void preOrderTraverse(BinaryTree *root){
        cout << (root -> data);                          //output the data of the root

        if (root -> left != NULL)
                preOrderTraverse(root -> left);  //traverse down to the left side of the tree
               
        if (root -> right != NULL)         
                preOrderTraverse(root -> right); //traverse down to the right side of the tree       
               
} //end preOrderTraverse()


void postOrderTraverse(BinaryTree *root){       

        if (root -> left != NULL)
                postOrderTraverse(root -> left);  //traverse down to the left side of the tree
       
        if (root -> left != NULL)               
                postOrderTraverse(root -> right); //traverse down to the right side of the tree
               
        cout << (root -> data);              //output the data of the root
       
} //end postOrderTraverse()


void inOrderTraverse(BinaryTree *root){         

        if (root -> left != NULL)
                inOrderTraverse(root -> left);  //traverse down to the left side of the tree
               
        cout << (root -> data);              //output the data of the root       
       
        if (root -> left != NULL)               
                inOrderTraverse(root -> right); //traverse down to the right side of the tree
       
} //end inOrderTraverse()


double evaluate(BinaryTree *root){
        double temp, divisor;
       
        if (isdigit(root -> data))      //if the data character is a number
                temp = (root -> data) - 48;  //convert char to the respective int/double value (48 is the ascii offset)
               
               
        if (isOperator(root -> data)){  //if the data character is an operator
       
                switch (root -> data){  //apply the operator to the left and right values using recursive traversal
               
                        case '+':
                                temp = evaluate(root -> left) + evaluate(root -> right);
                                break;
                               
                        case '-':
                                temp = evaluate(root -> left) - evaluate(root -> right);
                                break;
                               
                        case '*':
                                temp = evaluate(root -> left) * evaluate(root -> right);
                                break;
                               
                        case '/':
                                divisor = evaluate(root -> right); 
                               
                                if (divisor == 0){  //in math, you cannot divide by 0
                                        cout << "\nDivide by 0 error.\n";
                                        exit(1);
                                }
                               
                                else    //it's not 0, we can divide by it
                                        temp = evaluate(root -> left) / divisor;
                                       
                                break;
                               
                        case '^':
                                temp = pow(evaluate(root -> left), evaluate(root -> right)); //raises the first arg to the second arg
                                break;
                               
                        default:
                                cout << "\nError, operator unknown\n";
                                break;       
                         
                }
       
        }       
               
        return temp;
} //end evaluate()


bool isOperator(char ch){
        string acceptedOperators = "+-*/^";
       
        if(acceptedOperators.find(ch, 0) != string::npos)    //if ch can't be found in the string
                return true;
               
        else
                return false;
               
} //end isOperator()


void changecolor(char* word, int color){
        textcolor(color);                  //changes text to the color given through the argument
        cprintf("%s", word);                      //outputs the string in the given color
        textcolor(LIGHTGRAY);        //change color back to the default light gray
} //end changecolor()


void flushin(){

        while (cin.get() != '\n'){}  //clear the input buffer
       
} //end flushin()

---

My finished code.

It works for the most part. Unfortunately, it doesn't like equations like "(((3+4)*6)/7)" even though it should. Anyone able to spot why?

It must be something small, this entire program works fairly well