# Inserting infix into a binary tree

Show 80 post(s) from this thread on one page
Page 2 of 2 First 12
• 01-20-2003
Nick
This shows the general technique of recursive descent.
It evaluates expressions like
4 + (((3 + 5) * 6 + 8 + 4));
val = 64

Code:

```#include <iostream> using std::cout; using std::cin; using std::endl; /*   start->expr;   expr-> term | term + expr | term - expr   term-> factor * term | factor / term | factor   factor-> (expr) | num   num-> [0..N] */ enum { END_FILE, END_STATEMENT, PLUS, MINUS,       MULTIPLY, DIVIDE, LEFT_PARAN, RIGHT_PARAN, NUMBER}; struct Token {     int type;     int val; }; void read_next_token(); bool match(int token_type); int start(); int expr(); int term(); int factor(); Token next_token; int main(void) {     int val;         read_next_token();     val = start();     cout << "val = " <<  val << endl;     return 0; }         void read_next_token() {     int c;     next_token.type = END_FILE;     next_token.val  = 0;         while((c = cin.get()) && isspace(c))         continue;     if (isdigit(c)) {         int n = 0;                 cin.putback(c);         cin >> n;         next_token.type = NUMBER;         next_token.val  = n;         return;     }         switch(c) {     case ';':         next_token.type = END_STATEMENT;         break;     case '+':         next_token.type = PLUS;         break;     case '-':         next_token.type = MINUS;         break;     case '*':         next_token.type = MULTIPLY;         break;     case '/':         next_token.type = DIVIDE;         break;     case '(':         next_token.type = LEFT_PARAN;         break;     case ')':         next_token.type = RIGHT_PARAN;         break;     } } bool match(int token_type) {     bool ret;         if (next_token.type == token_type) {         read_next_token();         ret = true;     } else {         ret = false;     }     return ret; } int start() {     int val = expr();     return val; } int expr() {     int val = 0;     val = term();     switch(next_token.type) {     case PLUS:         match(PLUS);         val += expr();         break;     case MINUS:         match(MINUS);         val -= expr();         break;     default:         break;     }       return val; } int term() {     int val;     val = factor();     switch(next_token.type) {     case MULTIPLY:         match(MULTIPLY);         val *= term();         break;     case DIVIDE:         match(DIVIDE);         val /= term();         break;     default:         break;     }     return val; }     int factor() {     int val = 0;         switch(next_token.type) {     case NUMBER:         val = next_token.val;         match(NUMBER);         break;     case LEFT_PARAN:         match(LEFT_PARAN);         val = expr();         match(RIGHT_PARAN);         break;     default:         break;     }         return val; }```
• 01-20-2003
Nakeerb
Urg I just give up. I am never going to get this done. the struct is a simple

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

that's it.

I don't know how I'd insert into a tree using recursive descent either. No idea whatsoever
• 01-20-2003
Nick
It's easy to insert using recursive descent.

Code:

```int factor() {     int val = 0;         switch(next_token.type) {     case NUMBER:         val = next_token.val;         match(NUMBER);         break;     case LEFT_PARAN:         match(LEFT_PARAN);         val = expr();         match(RIGHT_PARAN);         break;     default:         break;     }         return val; }```
What type of tree would generate if next_token.type is
a NUMBER like 4? Just a single node tree with
'4'
What about a left param? Just a single node tree
'('

Now how would you code expr

Code:

```int expr() {     int val = 0;     val = term();     switch(next_token.type) {     case PLUS:         match(PLUS);         val += expr();         break;     case MINUS:         match(MINUS);         val -= expr();         break;     default:         break;     }       return val; }```
You would first generate a tree from term. Call that
tree left. Set right = 0.
If next_token.type == PLUS you generate
a tree from expr and assign that to right. Similarly for
next_token.type == MINUS. Then to generate the tree
for expr you would right something like this
Code:

```if (right != 0) {       root = new_node(left, right); } else {       root = left; }```
It's really easy for all of the functions. Just add a little error
checking in match and your finished.
• 01-20-2003
Nick
I'm not going to show you the code because that
would cheating but I was able to modifiy it to do
preorder, postorder and inorder traversals in only 230 lines.
The protypes of the functions are

bool match(int token_type);
Node* start();
Node* expr();
Node* term();
Node* factor();
void inorder(Node* root);
void postorder(Node* root);
void preorder(Node* root);
• 01-20-2003
Nakeerb
Is there any place I can talk to you besides this board?
• 01-20-2003
Nakeerb
Code:

``` void traverseInOrder(node *root){                 if (!root)                //test first to see if done                 return;                         traverseInOrder(root->left);         cout << root->data << " ";                traverseInOrder(root->right);          } void traversePreOrder(node *root){                 if (!root)                //test first to see if done                 return;                         cout << root -> data << " ";                        traversePreOrder(root -> left);         traversePreOrder(root -> right);        } void traversePostOrder(node *root){                 if (!root)                //test first to see if done                 return;                         traversePostOrder(root -> left);         traversePostOrder(root -> right);         cout << root -> data << " ";        }```
I can get those three of your list
Show 80 post(s) from this thread on one page
Page 2 of 2 First 12