# Thread: Inserting infix into a binary tree

1. 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;
};

bool match(int token_type);
int start();
int expr();
int term();
int factor();

Token next_token;

int main(void)
{
int val;

val = start();
cout << "val = " <<  val << endl;
return 0;
}

{
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) {
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;
}```

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

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

4. 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);

5. Is there any place I can talk to you besides this board?

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

Popular pages Recent additions