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